AProgrammableRouterArchitectureSupporting
`ControlPlaneExtensibility
`JunGao
`PeterSteenkiste
`EduardoTakahashi
`AllanFisher
`March
`CMU-CS--
`SchoolofComputerScience
`CarnegieMellonUniversity
`Pittsburgh,PA 
`Thisreportisanexpandedversionof\AProgrammableRouterArchitectureSupportingControl
`PlaneExtensibility,"IEEECommunicationsMagazine,( ) : - ,March.
`ThisresearchwassponsoredbytheDefenseAdvancedResearchProjectsAgencyandmonitoredbyNCCOSC
`RDTEDivision,SanDiego,CA  -,undercontractN - -C-andbyAFRL/IFGA,RomeNY
`  -,undercontractF - - - .
`Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorsandshouldnotbeinterpreted
`asrepresentingtheo(cid:14)cialpolicies,eitherexpressedorimplied,oftheDefenseAdvancedResearchProjectsAgency
`ortheU.S.government.
`
`IPR2018-01413
`Sony EX1035 Page 1
`
`

`

`Keywords:ProgrammableNetworks,ActiveNetworks,ControlPlaneExtensibility,Mobile
`Code
`
`IPR2018-01413
`Sony EX1035 Page 2
`
`

`

`Abstract
`TheInternetisevolvingfromaninfrastructurethatprovidesbasiccommunicationservicesintoa
`moresophisticatedinfrastructurethatsupportsawiderangeofelectronicservicessuchasvirtual
`realitygamesandrichmultimediaretrievalservices.However,thisevolutionishappeningonly
`slowly,inpartbecausethecommunicationinfrastructureistoorigid.Inthisreport,wepresent
`aprogrammablerouterarchitecture,inwhichthecontrolplanefunctionalityoftheroutercanbe
`extendeddynamicallythroughtheuseofdelegates.Delegatescancontrolthebehavioroftherouter
`throughawellde(cid:12)nedroutercontrolinterface,allowingserviceprovidersandthird-partysoftware
`vendorstoimplementcustomizedtra(cid:14)ccontrolpoliciesorprotocols.WedescribeDarwin,asystem
`thatimplementssuchanarchitecture.Weemphasizetheruntimeenvironmentthesystemprovides
`fordelegateexecutionandtheprogramminginterfacethesystemexportstosupportdelegates.We
`demonstratetheadvantagesofusingthissystembypresentingseveraldelegateexamples.
`
`IPR2018-01413
`Sony EX1035 Page 3
`
`

`

`Introduction
`
`TheInternethasevolvedfromabasicbitwaypipetoamoresophisticatedinfrastructurethat
`supportselectronicservices.Theservicestodayarefairlyprimitiveandaretypicallyrelatedto
`collectinginformationovertheWeb.Richerservicessuchashigh-qualityvideoconferencing,virtual
`realitygames,anddistributedsimulationhavebeenpromised.Progressisslowinpartbecause
`theinfrastructureisin(cid:13)exible.Routersareclosedboxesthatexecutearestrictedsetofvendor
`software.Computeandstorageserversaretypicallydedicatedtosupportonetypeofservice.An
`alternatearchitectureistohaveanopeninfrastructureinwhichspeci(cid:12)cservicescanbeinstalled
`andinstantiatedondemand,muchlikewhatwedoonaPCtoday.Oneoftheadvantagesofthis
`approachisthatitallowsalargercommunityofpeopletodevelopservices,whichspursinnovation.
`Weusesomeexamplestomotivatethisapproach.
`The(cid:12)rstclassofexamplesaddressesthecustomizationoftra(cid:14)ccontrolandmanagement.
`Today,therangeoftra(cid:14)cmanagementoptionsisfairlylimited.Whileswitchesandroutersin-
`creasinglyhavesomesupportforclassi(cid:12)cationandscheduling,thesecapabilitiesareoftenonlyused
`insimpleways,suchasto(cid:12)lteroutcertaintypesoftra(cid:14)c,todosomesimpleprioritizationof(cid:13)ows,
`ortoimplementstandardizedQoSmechanismssuchasdi(cid:11)erentiatedservices.Onecouldenvision
`thatuserscouldemploythesemechanismstohandletheirtra(cid:14)cinspeci(cid:12)cways.Forexample,one
`serviceprovidercouldimplementgold/silver/bronzeservicedi(cid:11)erentiationinaproprietaryway,
`whileanotherserviceproviderimplementscommunicationserviceswithstrongerguarantees.Simi-
`larly,onecouldenvisiondeployingavirtualprivatenetwork(VPN)service,inwhichVPNscanuse
`di(cid:11)erenttra(cid:14)ccontrolpoliciesorcontrolprotocols.
`Thesecondclassofexamplesconsistsofvalue-addedservices,thatis,servicesthatrequire
`notonlycommunication,butalsodataprocessingandaccesstostorage.Examplesincludevideo-
`conferencingwithvideotranscodingandmixingsupport,customizedWebsearchingservices,and
`application-speci(cid:12)cmulticast.Whileitispossibletodelivertheseservicesusingasetofdedicated
`servers,itwouldbemoree(cid:14)cientifservicescoulddeployeddynamicallyonserversleasedonanas
`neededbasis.Thiswouldallowtheservicetoadapttothedemandsandlocationsofthecustomers.
`Value-addedservicescanalsobene(cid:12)tfromcustomizedtra(cid:14)cmanagementsupport.Forexample,
`avirtualrealitygameserviceprovidermaywanttohandlecontrol,audio,andvideotra(cid:14)c(cid:13)ows
`indi(cid:11)erentways.Thismayrequirecustomizedtra(cid:14)ccontrolpoliciesontherouter.
`Aslongasroutersareclosedboxesthatareshippedwithasetofstandardprotocols,itisunlikely
`thattheseexampleswillberealized.Theaboveexamplescanbestbesupportedbyaprogrammable
`networkinfrastructure.Suchanetworkwillallowcomputing,storage,andcommunicationresources
`tobeallocatedandprogrammedtodeliveraspeci(cid:12)cservice.Standards(e.g.,ODBC,POSIX)
`existtousestorageservers(Web,(cid:12)lesystems,databases)andcomputeservers.Routers(i.e.,
`communicatinservers),however,arenotprogrammabletoday.Inthisreportwepresentarouter
`architectureinwhichthecontrolplanefunctionalityoftheroutercanbeextendedusingdelegates,
`codesegmentsthatimplementcustomizedtra(cid:14)ccontrolpoliciesorprotocols.Delegatescana(cid:11)ect
`howtheroutertreatsthepacketsbelongingtoaspeci(cid:12)cuserthroughtheroutercontrolinterface
`(RCI).Withthisarchitecture,abroadercommunity(e.g.,thirdpartysoftwarevendorsorvalue-
`addedserviceproviders)candevelopapplicationsforrouters.
`Theremainderofthereportisorganizedasfollows.We(cid:12)rstde(cid:12)neanetworkarchitecturein
`Sectioninwhichnetworkfunctions(e.g.,QoS)canbeselectivelycustomizedtomeetthespecial
`needsofusers.
`InSection ,wedescribeDarwin,aspeci(cid:12)cinstanceoftheabovearchitecture.
`Wefocusontheruntimeenvironmentfordelegates,codesegmentsthatcancustomizenetwork
`controlandmanagement.InSectionwepresentsomeexamplesofhowdelegatescanbeapplied
`toaddressavarietyofresourcemanagementandtra(cid:14)ccontrolproblems,andwediscusssecurity
`
`
`IPR2018-01413
`Sony EX1035 Page 4
`
`

`

`issuesraisedbytheuseofdelegatesinSection.Finally,wepresentrelatedworkinSectionand
`concludethereportinSection.
`AProgrammableNetworkArchitecture
`We(cid:12)rstcharacterizethenetworkprogrammabilityrequirementsandintroducetheconceptofa
`delegate.Wethenpresentaprogrammablenetworkarchitecturethatcansupportdelegates.
`. Networkprogrammability
`Wecandistinguishbetweentwotypesofoperationsondata(cid:13)owsinsidethenetwork.The(cid:12)rst
`classinvolvesmanipulationofthedatainthepackets,suchasvideotranscoding,compression,
`orencryption.Sincemostroutersdonothavesigni(cid:12)cantgeneral-purposeprocessingpower,this
`typeofprocessingwilltypicallytakeplaceoncomputeservers(e.g.,workstationclustersinsidethe
`networkinfrastructure).Inthefuture,thesetaskscouldalsobeperformedonroutersthathave
`beenspeci(cid:12)callybuilttoalsoperformdataprocessing,besidestheusualroutingfunctions.The
`secondclassofoperationsondata(cid:13)owschangeshowthedataisforwardedbuttypicallydoesnot
`requireprocessingorevenlookingatthebodyofpackets.Examplesincludetunneling,rerouting,
`selectivepacketdropping,andchangingthebandwidthallocationofa(cid:13)ow.Thenatureofthese
`operationsissuchthattheyarebestexecutedonroutersorswitches.
`Wecallthecodesegmentsthatperformthesetasksdelegatessincetheyrepresenttheowner
`ofthedata(cid:13)owsinsidethenetwork.Datadelegatesperformdataprocessingoperationsand
`executeoncomputeserversorspeciallydesignedrouters.Controldelegatesexecuteonrouters
`andareinvolvedinthecontrolofdata(cid:13)ows.Thissimpleclassi(cid:12)cationofdelegatesissomewhat
`arti(cid:12)cialsincesomedelegatesmayfallinbetweenthesetwoclasses.Forexample,adelegatethat
`isconcernedwithcontrolmayneedtolookatthepacketbodytodecidehowtohandlepackets.
`Similarly,a\mostlycontrol"delegatemayonrareoccasionshavetomodifyapacket.Nevertheless,
`thedistinctionisusefulbecausethetwoclassesofdelegatesimposeverydi(cid:11)erentrequirementson
`thesystemonwhichtheyrun.Controldelegatesrequireanenvironmentthatprovidesarichset
`ofmechanismstocontroldata(cid:13)ows,whiledatadelegatesmustrunonaplatformwithsubstantial
`computationalpower.
`Whilenobodyislikelytoargueagainsttheuseofdatadelegatesoncomputeserversfordata
`processing,theneedforcontroldelegatesislessobvious.Onecouldimaginerouterswith(cid:12)xed
`functionality,similartotoday'srouters,whereuserscancontrolhowtheirtra(cid:14)c(cid:13)owsarehan-
`dledbypassingparameterstotheroutersusingasignallingprotocol.Theexamplesdiscussedin
`Section providesomereasonsthatdirectlyexecutingcode(i.e.,controldelegates)ontherouters
`maybeamoree(cid:11)ectivewaytocustomizetra(cid:14)ccontrolandmanagement.A(cid:12)rstreasonisthat
`controldelegatescanrespondmuchmorequicklytochangesinthetra(cid:14)cconditions;itwouldtake
`anentityattheedgeofthenetworkatleastoneandmorelikelyseveralround-triptimesbeforeit
`could(cid:12)rstobserveandthenrespondtoachangeinthenetwork.Second,itseemsimpracticalto
`identifyallpossibleuserrequirementsapriori,sothattheycanbeaddressedbythedefaultrouter
`software;anarchitecturebasedondelegatesismore(cid:13)exibleandextensible.Finally,supporting
`customizationbyextendingrouterfunctionalitymayoftenbeamorenaturalandthuslesserror-
`pronesolution.Forexample,ifaserviceproviderwantstousearoutingprotocolthatisoptimized
`foritstra(cid:14)c,doingsofromtheedgesofthenetworkislikelytobeunnecessarilycomplicated.
`
`
`IPR2018-01413
`Sony EX1035 Page 5
`
`

`

`Other Signalling Entities
`
`RCI
`
`Classifier
`
`Scheduler
`
`RouteLookUp
`
`Other
`Routing
`Entities
`
`Routing
`
`Signalling
`
`Delegates
`
`Other
`Delegates
`
`Local Resource Manager
`
`Figure :Nodearchitecture.
`.Routerarchitecture
`Figure presentsanodearchitecturethroughwhichdelegatescanbeaddedtoarouter.The
`architectureshowsacontrolplane(toppart)thatexecutescontrolprotocolssuchasroutingand
`signalling,andadataplane(bottompart)responsibleforpacketforwarding.Controldelegates
`executeinaspecialruntimeenvironmentthatispartofthecontrolplane.Thisdesignismotivated
`byboththeintendeduseofcontroldelegates(controlandmanagementoftra(cid:14)c(cid:13)ows)andpractical
`designconsiderations(wedonotwanttoaddunnecessarycomplexitytothedataforwardingpath,
`wherespeedandsimplicityarecritical).Onsomeroutersitmayalsobepossibletoinsertdata
`delegatesinthedataforwardingplane.
`Controldelegatescanchangehowtra(cid:14)cishandledinthedataforwardingplanethroughthe
`RCI.TheRCIprovidesasetofoperationson(cid:13)ows,sequencesofpacketswithasemanticrelation-
`shipde(cid:12)nedbyapplicationsandserviceproviders.Flowsarede(cid:12)nedoneachrouterusinga(cid:13)ow
`spec[],alistofconstraintsthat(cid:12)eldsinthepacketheadermustmatchforapackettobelong
`tothe(cid:13)ow.Theclassi(cid:12)erusesthe(cid:13)owspecstodeterminewhat(cid:13)owincomingpacketsbelongto.
`Classi(cid:12)cationshouldtakeplaceearlyinthedataforwardingpathsothatpacketscanbehandled
`appropriately.Some(cid:13)ow-speci(cid:12)cactions,suchastunnelingandrerouting,arebestexecutedon
`theinputinterface.ActionsontheoutputinterfacearegenerallyassociatedwithQoSrelated
`parameterssothatafterclassi(cid:12)cationtheschedulercanschedulethepacketsbelongtoeachclass
`accordinglytomeettheirQoSrequirements.
`WecanviewtheRCIasaninstructionsetthatoperateson(cid:13)owsasabasicdatatype.A
`criticaldesigndecisioninthearchitectureisthede(cid:12)nitionofthisinterface(whatfunctionsshould
`beexportedtothedelegates).TheRCIshouldbebroadenoughtosupportbothvalue-added
`servicesandnetworkmanagementapplications.HoweversincetheRCIwillbeusedbycontrol
`delegatesonrouters,e(cid:14)ciencyandsecurityissuesshouldalsobetakenintoaccount.Wewill
`elaborateonaspeci(cid:12)cimplementationoftheRCIlater.
`Mostofthecomponentsintheproposedrouterarchitecturecanalsobefoundinarchitectures
`designedtosupportqualityofservice(QoS)intheInternet.Forexample,thepacketclassi(cid:12)cation
`andschedulingmodulesarepresentintheInternetEngineeringTaskForce(IETF)integrated
`servicesmodel[, ]andthemorerecentdi(cid:11)erentiatedservicesmodel[ ],[].Thedi(cid:11)erence
`liesinthatthisarchitectureprovidingprogrammabilityinthecontrolplanethroughtheuseof
`delegatesandtheRCIprogramminginterface,RCI.
`
`IPR2018-01413
`Sony EX1035 Page 6
`
`

`

` DarwinDelegates
`WegiveabriefoverviewoftheDarwin[]systemanddescribetheDarwinRCIanddelegate
`runtimeenvironment.
` . Darwindelegatedesign
`TheDarwinprojectdevelopedasetofcustomizableresourcemanagementmechanisms.Customiz-
`abilityallowsapplicationsandserviceproviderstotailorresourcemanagement,andthusservice
`quality,to(cid:12)ttheirneeds.Darwinincludesthreemechanismsthatoperateondi(cid:11)erenttimescales.
`Aresourcebroker,calledXena,selectsresourcesthatmeetapplicationneedsusingapplication-
`speci(cid:12)edmetricstooptimizeresourceutilization[ ].Delegatessupportcustomizableruntimere-
`sourcemanagement,asdescribedabove.Finally,Darwinusesahierarchicalpacketschedulerthat
`supportsawiderangeofpoliciesandintegratesper-(cid:13)owQoSandlinksharinginasingleframe-
`work[].Theactivitiesofthethreemechanismsarecoordinatedbyasignallingprotocolcalled
`Beagle[ ].
`Darwindelegatesarebasedonthearchitectureoutlinedintheprevioussection,butthear-
`chitectureisextendedintwoways.First,inDarwintheclassi(cid:12)erthatidenti(cid:12)es(cid:13)owsusesnot
`onlythestandard(cid:12)eldsintheIPandtransportheaders(IPaddresses,portnumbers,andprotocol
`identi(cid:12)er),butalsoanoptionalapplicationidenti(cid:12)er.Thisallowsservicestode(cid:12)ne(cid:13)owsbasedon
`theirownsemantics.Anexampleislayeredvideo,wheredi(cid:11)erentlayersaretaggedwithadi(cid:11)erent
`applicationidenti(cid:12)er.
`Inourcurrentimplementation,theapplicationidenti(cid:12)erisstoredinthe
`packetasanIPoption.Otherformats(e.g.,theIPv(cid:13)owID)arepossible.Everypacketshould
`normallybeclassi(cid:12)edonce,soonafteritarrivesontherouter.
`InDarwin,forimplementation
`convenience,weusetwoclassi(cid:12)cationengines,oneattheinputportandtheotherattheoutput
`port.Theextraclassi(cid:12)cationaddsnegligibleoverheadinoursystem.
`Figure:Exampleresourcetree.
`Second,Darwinmanagessresourcesinahierarchicalfashion.Thismeansthattheresource
`distributionofalinkisrepresentedbyaresourcetree(Figure),withtherootrepresentingthe
`link,leafnodesactualdata(cid:13)ows,andinteriornodesorganizations,servicesorapplicationsthat
`controlthe(cid:13)owor(cid:13)owaggregatecorrespondingtotheirchildren.Resourceallocationpoliciescan
`bespeci(cid:12)edforbothleafandinteriornodes,sobothper-(cid:13)owQoSandlinksharingcanbesup-
`portedinthesameframework.Thiscanbeviewedasa\divide-and-conquer"approachtoresource
`management.Thebandwidthofalink(rootnode)canbedividedacrossasetoforganizations
`(childrenoftheroot),eachofwhichcanmanageitsbandwidthsharebyconstructinganappro-
`priatesubtree.DarwinusestheHierarchicalFairServiceCurvescheduler[],whichhasexcellent
`
`
`Controlled
`Load Service
`
`60 Mbps
`
`Org 1
`
`30 Mbps
`Serv 1
`
`40 Mbps
`
`Org 2
`
`Guaranteed
`Service
`
`10 Mbps
`Serv 2
`
`Serv 3
`
`Seminar
` video
`
`Seminar
` audio
`
`Distributed
`Simulation
`
`WEB
`
`Control
`
`Audio
`
`Video
`
`155 Mbps
`
`Link
`
`100 Mbps
`
`Provider 1
`
`55 Mbps
`
`Provider 2
`
`Best-effort
`Service
`
`IPR2018-01413
`Sony EX1035 Page 7
`
`

`

`Org2
`
`
`
`
`
`
`
`
`
`
`App1
`
`
`
`
`
`Flow1
`
`
`
`
`
`
`
`
`
`
`Link
`
`Org1
`
`Control Delegates
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`isolationproperties;changesinthestructureorpoliciesofonesubtreedonota(cid:11)ectthewaytra(cid:14)c
`controlledbyothersubtreesishandled.
`Figure :Pairingcustomizationinthecontrolanddataplane.
`Thecombinationofdelegates(inthecontrolplane)andhierarchicalresourcemanagement
`(inthedataplane)providesanexcellentframeworkforthecustomizationoftra(cid:14)ccontroland
`management.Weemphasizedearlierthatoneuseofdelegatesistocustomizehowaspeci(cid:12)c
`setof(cid:13)owsishandled.Thisisachievedbyassociatingadelegatewithaspeci(cid:12)cnodeinthe(cid:13)ow
`hierarchy(Figure ),sothedelegateoperatesonlyon(cid:13)owsassociatedwiththatnodeanditssubtree
`andcannota(cid:11)ectother(cid:13)ows.Inotherwords,thehierarchicalschedulerprovidestheisolationof
`networkresourcesinthedataplaneandthematchinghierarchicaldelegatesprovidetheisolation
`oftra(cid:14)cmanagementandcontrolinthecontrolplane.Notethatsomedelegatesmayoperateon
`thenetworkasawhole;suchdelegatesarelogicallyassociatedwiththeroot.
` .RouterControlInterface
`Wedescribe(cid:12)veclassesoffunctionsthatarenecessaryfortheRCItosupportabroadspectrum
`ofdelegates.
` .. Flowmanipulationmethods
`TheRCIpresentsdelegateswitha(cid:13)ow-basedprogrammingmodel.Thisclassofmethodsallows
`delegatestode(cid:12)neandmanage(cid:13)owsbyupdatingtheclassi(cid:12)erdatastructures.Forexample,a
`(cid:13)owde(cid:12)nedwitha(cid:13)owspec(alistofheader(cid:12)elds)canbeaddedtotheclassi(cid:12)erthroughthe
`add(cid:13)owcall.Ahandlecorrespondingtothis(cid:13)owisreturned.Subsequenttreatmentonthis(cid:13)ow,
`suchasspecifyingQoSparametersortra(cid:14)credirectingparameters,arethenperformedusingthis
`handle.Fourmethodsareavailableforvarious(cid:13)owmanipulation.
`add(cid:13)ow(interfacename,(cid:13)owspec)createsa(cid:13)owwith(cid:13)owspeconthegiveninterfaceand
`returnsa(cid:13)owidtothecaller;
`delete(cid:13)ow(interfacename,(cid:13)owid)removesthe(cid:13)owwith(cid:13)owidfromthespeci(cid:12)edinterface;
`modify(cid:13)ow(interfacename,(cid:13)owid,new(cid:13)owspec)changesthe(cid:13)owspecofthe(cid:13)owwith
`(cid:13)owidtonew(cid:13)owspecandreturnsanew(cid:13)owid;
`retrieve(cid:13)owspec(interfacename,(cid:13)owid)returnsthe(cid:13)owspecofthe(cid:13)owwith(cid:13)owid.
`
`
`IPR2018-01413
`Sony EX1035 Page 8
`
`

`

` ..Resourcemanagementmethods
`Delegateschangehowresourcesareallocatedanddistributedacross(cid:13)owsbymodifyingstatesin
`theschedulerthroughtheRCI.Theschedulerreliesonitshierarchicalresourcetreetoschedule
`packetstomeeteach(cid:13)ow'sQoSrequirement.Anodeintheresourcetreeisidenti(cid:12)edbyanodeid,
`andmaycorrespondtomultiple(cid:13)ows.EachresourcetreenodeisassignedasetofQoSparameters
`tospecifytheservicethatthe(cid:13)owsbelongingtothisnodewillreceive.Theprecisenatureofthis
`classoffunctionsdependsonthescheduler,andthefunctionslistedbelowinourimplementation
`shouldberepresentativeofmosthierarchicalschedulers.
`createnode(interfacename,parentnodeid)createsachildnodeforthenodewithparentnodeid
`andreturnsanodeid.Bydefault,therootnodewhichcorrespondstothetotalresourceofan
`interfaceiscreatedatthesystemstartuptime;
`deletenode(interfacename,nodeid)deletesthenodewithnodeidfromtheresourcetree;
`reserveservice(interfacename,nodeid,serviceparameters)triestoreserveservicesspeci(cid:12)ed
`inserviceparametersforthenodewithnodeid.Thiscallissubjecttoresourceadmissioncontrol,
`andifitreturnssuccessfully,(cid:13)owsbelongingtothisnodewillreceivetheservicereserved.
`modifyservice(interfacename,nodeid,serviceparameters)triestochangeservicesforthe
`nodewithnodeidaccordingtotheserviceparametersspeci(cid:12)edinserviceparameters.Thiscall
`isalsosubjecttoresourceadmissioncontrol,andifitreturnssuccessfully,(cid:13)owsbelongingtothis
`nodewillreceivetheservicede(cid:12)nedbyserviceparameters;
`add(cid:13)owtonode(interfacename,nodeid,(cid:13)owid)addsthe(cid:13)owwith(cid:13)owidtothesetof
`(cid:13)owsthatbelongtothenodewithnodeid.Thisbasicallygrantsthe(cid:13)owwiththeservicethatthe
`nodehas;
`del(cid:13)owfromnode(interfacename,nodeid,(cid:13)owid)removesthe(cid:13)owwith(cid:13)owidfromthe
`setof(cid:13)owsthatbelongtothenodewithnodeid.Bycallingthismethod,a(cid:13)ow'sservicecanbe
`revoked;
`retrievetree(interfacename,nodeid)returnstheresourcetreehierarchyrootedatthenode
`withnodeid;
`retrieve(cid:13)ows(interfacename,nodeid)returnsthelistof(cid:13)owid'sassociatedwiththenode
`withnodeid.
` .. Flowredirectingmethods
`Asopposedtotheaboveclassofmethods,whichhaveonly\local"meaning,theRCImethodsin
`thisclasshave\global"meaninginthattheymaya(cid:11)ectthetra(cid:14)cdistributioninthenetwork.
`Delegatesusetheassociateactionmethodtobindcertainactionswith(cid:13)owsfor(cid:13)owredirecting
`purposes.Forexample,adelegatecanreroutea(cid:13)ow'spacketsusingarouteotherthanthedefault
`toavoidhotspotsinthenetwork.WhiletheresourcemanagementRCIcallstypicallycontrola
`router'soutputportfunctionalities,the(cid:13)owredirectionactionstypicallytakeplaceontheinput
`port.associateaction(intefacename,(cid:13)owid,actiondata)associatestheproperactiondatare-
`quiredtothe(cid:13)owwith(cid:13)owid.
`Currentlythreeactionsaresupported:
`tunneling:theactiondatafortunnelingistwoencapsulationIPaddresses:encapsrcaddr
`andencapdstaddr.Thepacketsbelongingtothis(cid:13)owwillbeprependedwithanextraheader
`usingencapsrcaddrandencapdstaddrassourceanddestinationaddresses.Byassociatingthis
`actionwitha(cid:13)ow,adelegatecanredirectthe(cid:13)ow'spacketstoaselecteddestination;
`rerouting:theactiondataforreroutingisnexthopaddr,whichisthenexthopaddressthat
`
`
`IPR2018-01413
`Sony EX1035 Page 9
`
`

`

`this(cid:13)ow'spacketswillbeforwardedto.Thiswillenablethedataplaneoftheroutertoskiptheusual
`routingtablelookupandforwardpacketsusingtheinterfacethatcorrespondstonexthopaddr;
`dropping:dropsa(cid:13)ow'spacketsattheinputport.
`Themethodretrieveaction(interfacename,(cid:13)owid)returnstheactiondatathatassociates
`withthe(cid:13)owwith(cid:13)owid.
`Methodsofdirectoperationonarouter'sroutingtablecanbeusedbydelegatesthathavesuperuser
`privileges.Thesemethodsdonotoperateonaper-(cid:13)owbasis.
`getroute(dstaddr)retrievesnexthopaddressfromtheroutingtablefordstaddr;
`changeroute(dstaddr,nexthopaddr)updatesthenexthopaddressintheroutingtableentry
`fordstaddrtonexthopaddr,andthisrequiressuperuserprivilege.
` ..Networkstatusmonitoringmethods
`Thisclassofmethodsallowsdelegatestoprobecertainnetworkstates,e.g.,queueoccupancy,kernel
`statisticscounters,error(cid:13)ags,etc.Itcanalsoinvolvepostingrequestsfornoti(cid:12)cationfromthe
`kernelofasetofspeci(cid:12)cevents,suchascrossingofaqueueoccupancythresholdandoccurrence
`ofafailurecondition.Bymonitoringthenetworkstatususingthesemethods,adelegatecan
`intelligentlytakeotherproperactionsinatimelyfashionaccordingtowhatithasobserved.For
`example,adelegatemaysetupathresholdforaparticular(cid:13)ow'squeueusingthesetmethod,
`andlateroncanperiodicallyquerythequeuelengthbycallingtheprobemethod.Thiscanalso
`bedonebysettingupanasynchronousnoti(cid:12)cationwiththekernelusingtherequestmethod.
`Thiswaythekernelcansignalthedelegatewheneverthequeuelengthistoolong.Asanother
`example,adelegatecanturnonthemonitormodeinthekernelbyusingmonitoronmethod,and
`thenretrievepacketcountersinthekernelthroughretrievedatamethodtocomputetheaverage
`bandwidthusageofaparticular(cid:13)ow.
` ..Supportfordelegatecommunication
`Delegatescansetupcommunicationchannelstocoordinateactivitieswithpeersonotherrouters
`andinteractwiththeapplicationonendpoints.Messagingbetweenthemallowsdelegatestogather
`globalinformationsothatproperglobalactionsmaybetaken,suchasreroutingforloadbalancing.
`Interactionwithapplicationsonend-pointsincreasesthe(cid:13)exibilityofthesystem,asadaptation
`tonetworkeventstypicallyinvolvesthesources.Inter-delegatecommunicationisoftenapplication
`speci(cid:12)c.Webuiltthecommunicationchannelsbetweendelegatesontopofstandardcommunication
`methods.
` ..Othermethods
`Theabove(cid:12)veclassesoffunctionsarelikelytobeappropriateformostrouters.However,individual
`routersmayhaveadditionalfunctionalityontheirdataforwardingpathandmayallowdelegates
`tocontrolthesefunctions.Asanexample,onarouterthatsupportsrandomearlydetection
`(RED),delegatesmaybeabletochangethethresholdsusedtotriggerearlypacketdrops.Ona
`Di(cid:11)Servedgerouter,delegatesmayneedaccesstothecontrolparametersforshapersandmeters.
`Otherroutersmayhavealgorithmstoidentifynon-conformant(cid:13)owsandmayallowdelegatestoget
`accesstothisinformation;wewillgiveanexampleusingthisfunctionalityinSection.Clearly,an
`interfacestandardlikemanagementinformationbase(MIB)de(cid:12)nitionsfornetworkmanagement
`wouldhavetobeextensible,sonewcallscanbeaddedastechnologyevolves.
`
`
`IPR2018-01413
`Sony EX1035 Page 10
`
`

`

` . Delegateimplementation
`DarwindelegatesarebasedonJavaandusetheJDK .Javavirtualmachine(JVM)fromSun
`Microsystems[ ].Thisenvironmentgivesusacceptableperformance,portability,andsafety
`featuresinheritedfromthelanguage.DelegatesareexecutedasJavathreadsinsidethevirtual
`machine\sandbox".AdelegateischaracterizedbyitsQoSrequirement(e.g.,theamountofCPU
`andmemoryresourcesneeded),andruntimeenvironmentneeded.
`ExperimentstomeasuretheoverheadoftheRCIcallsfromwithinthedelegateruntimeenvi-
`ronmentshowedminimaldi(cid:11)erencebetweencallsfromJavadelegatesandcallsfromequivalentC
`programs.ThatisareasonableresultsinceRCIcallsareactuallyimplementedasnativemethods.
`Theoverheadofmostdelegatescallsinanunloadedsystemismeasuredtobearoundmicrosec-
`ondsusingmachinesinourtestbed(seeSection).Asthesystemloadincreases(e.g.,withpacket
`forwarding)thesystemcalllatencybecomeshighlyvariableandunpredictablesinceouroperating
`systemsdonoto(cid:11)erreal-timeguarantees.
`DelegatesareinstalledthroughtheDarwinsignallingprotocol,Beagle,usingamulti-steppro-
`cess.First,theapplicationorserviceprovidersubmitsdelegateJavabytecode,delegateresource
`andruntimerequirements,togetherwithalistof(cid:13)owspecstoBeagle.Second,Beagletransports
`thisinformationtoBeagledaemonsrunningontherelevantrouters.Third,eachBeagledaemon
`performslocaladmissioncontrolforboththe(cid:13)owsand(ifnecessary)anydelegates.Fordelegates,
`thisincludesverifyingthatthedelegateruntimeenvironmenthastherequiredlibrariestosup-
`portthedelegate.Atthispoint,Beagleshouldalsoverifythattherouterhassu(cid:14)cientCPUand
`memoryresourcestoaccommodatethedelegate,butsinceourenvironment(PC-basedrouters)can
`notexplicitlymanagetheseresources,thisstepisnotimplemented.Finally,ifadmissioncontrol
`succeeds,Beaglethensetsupthe(cid:13)owsbymakingappropriatecallstotheclassi(cid:12)erandscheduler,
`passesthebytecodetothedelegateruntimeenvironmenttostartupthedelegate,andthenpasses
`thedelegateasetofhandlesidentifyingthe(cid:13)owsforwhichitisresponsible.Theinterfacethatis
`usedbyBeagletostartdelegatesisdescribedinmoredetailelsewhere[ ].
`DelegateswritteninCarealsosupportedinoursystembutinamuchmorerestrictiveway.
`Datadelegatesthatrunoncomputeserverscanbesetupinasimilarfashion.
`Delegatesareaveryfocusedapplicationofactivenetworking[]:theyareinstalledasyn-
`chronouslyfromtherestofthedatatra(cid:14)cbyaseparatesignallingprotocolonaper-application
`orper-servicebasis;adelegatecanonlyoperateonthe(cid:13)owsthatitisassociatedwith.Asisthe
`casewithactivenetworkingingeneral,delegatesraisesigni(cid:12)cantsafetyandsecurityconcerns.In
`Sectionwewilldiscusssafetyandsecurityissuesrelatedtodelegatesinmoredetails.
`Examples
`TheDarwinsystemhasbeenimplementedonFreeBSDandNetBSDPCrouters.Experiements
`wereperformedtotestthesystemonalocaltestbedshowninFigure.Thethreerouters,shown
`inboxes,arePentiumIIMHzPCsrunningtheDarwinkernelwhichisbuiltontopofFreeBSD
`...Theendsystemsm -m areDigitalAlpha A MHzworkstationsrunningDigital
`Unix..Alllinksarefull-duplexpoint-to-pointEthernetlinkscon(cid:12)gurableaseither Mbps
`or Mbps.Unlessspeci(cid:12)ed,thelinksarecon(cid:12)guredas Mbps.Inthissection,wepresent
`(cid:12)vedelegateexamplesandshowsomeexperimentalresultsobtainedfromthistestbed.The(cid:12)rst
`threeexamplesdemonstratehowapplicationspeci(cid:12)cservicescanbeaddedtothenetworkthrough
`delegatestoimprovethequalityofexecutionoftheseapplications.Thelasttwoexamplesshow
`thatdelegatescandynamicallycustomizetra(cid:14)ccontrolandmanagementinanetwork.
`
`
`IPR2018-01413
`Sony EX1035 Page 11
`
`

`

`21
`
`18.
`4
`
`19
`
`15
`
`8.4
`
`7.5
`
`0.4 0.5
`
`Shared
`
`Figure:DarwinIPtestbedtopology.
`Figure:Videoqualityunderfourscenarios.
`. SelectivepacketdroppingforMPEGvideostreams
`MPEGvideostreamsareverysensitivetorandompacketlossbecauseofthedependenciesbetween
`threedi(cid:11)erentframetypes:Iframes(intracoded)whichareselfcontained,Pframes(predictive)
`whichuseapreviousIorPframeformotioncompensationandthusdependonthispreviousframe,
`andBframes(bidirectional-predictive)whichuse(andthusdependon)previousandsubsequent
`IorPframes.Becauseoftheseinter-framedependencies,losingIframesduringtransmissionis
`extremelydamaging,whileBframesaretheleastcritical.Undercongestion,thereceivedvideo
`qualityisdegradedduetopacketlossbutthequalitycanbeenhancedifonlyBframesaredropped
`atthecongestedlinkinsteadofrandomframes(includingcrucialIframes)beingdropped.
`Delegatescanbeusedtoperformselectivepacketdroppingoncongestedrouters.Delegates
`areinjectedintoroutersthatmaypotentiallybecongested,andthesedelegatesareassociated
`withMPEG(cid:13)owsinthedataplane.Intheresourcehierarchy,a(cid:13)owissetuptocorrespondto
`theMPEGapplicationandthreesub-(cid:13)owsdi(cid:11)eringfromoneanotherintheapplicationidenti(cid:12)er
`(cid:12)eldinthe(cid:13)owspecarethenaddedtodi(cid:11)erentiatethethreedi(cid:11)erentframetypes.Packets
`belongingtodi(cid:11)erentframetypesaremarkedwithspeci(cid:12)capplicationidenti(cid:12)erssothattheywill
`beclassi(cid:12)edintodi(cid:11)erentsub-(cid:13)ows.DelegatesmonitorthequeuelengthoftheMPEG(cid:13)ow,and
`whencongestionisdetected(e.g.,thequeuelengthexceedssomepresetthreshold),delegateswill
`instructthedataplanetodropthepacketsbelongingtotheBframesub-(cid:13)ow,thusprotectingI
`andPframesfrombeingdroppedduetoqueueover(cid:13)ow.Asaresult,thereceiverwillobservea
`
`
`Reservation Sel. Drop A. Sel. Drop
`
`m2
`
`m6
`
`m4
`
`m7
`
`Flow 1
`
`Flow 2
`
`Timberline
`
`Maui
`
`Link 1
`10/100 Mbps
`
`Link 2
`100 Mbps
`
`Whiteface
`
`Flow 3
`
`Link 3
`100 Mbps
`
`m1
`
`m5
`
` m8
`
`m9
`
`m3
`
`25
`
`20
`
`15
`
`10
`
`5
`
`0
`
`Frame Rate (fps)
`
`IPR2018-01413
`Sony EX1035 Page 12
`
`

`

`gracefullydegradedquality.
`Experimentswereperformedonthetestbedtodemonstratethee(cid:11)ectivenessofselectivepacket
`discardingdelegates.ThreestreamsaresentovertheTimberline-Mauilink(bottlenecklink)of
`thetestbed:twoMPEGvideostreamsandoneunconstrainedUDPstream.TheUDPstream
`causescongestiononthislink.Bothvideosourcessendatarateof frames/second,andour
`performancemetricistherateofcorrectlyreceivedframes.Figurecomparestheperformanceof
`fourscenarios.Inthe(cid:12)rstscenario,thevideoandUDPdatapacketsaretreatedequally,andthe
`randompacketlossesresultinaverylowframerate,asexpected.Inthesecondcase,thevideo
`streamsshareabandwidthreservationwhichequalstothesumoftheaveragevideobandwidths.
`Thisimprovesperformance,butthevideostreamsarebursty,andrandompacketlossduringpeak
`transfersresultsinlessthanathirdoftheframesbeingreceivedcorrectly.Inthethirdscenario,we
`placeadelegateonTimberline.Asdescribedearlier,thedelegatemonitorsthelengthofqueueused
`byvideostreamsanddropstheBframeswhencongestionisobserved.Packetdroppingisswitched
`o(cid:11)whenthequeuesizedropsbelowalowerthreshold.Figureshowsthatisquitee(cid:11)ective:the
`framerateroughlydoubles.
`WhiledelegatesprovideanelegantwayofselectivelydroppingBframes,thesamee(cid:11)ectcould
`beachievedbyassociatingdi(cid:11)erentprioritieswithdi(cid:11)erentframetypes.Inscenariofourweusea
`delegatetoimplementamoresophisticatedcustomizeddroppolicy.Inscenariothree,eitherallor
`noneoftheBframesaredropped.BydroppingtheBframesofonlyasubsetofthevideostreams,
`wecanachieve(cid:12)nergraincongestioncontrol.Theadvantageofhavingadelegatecontrolselective
`packetdroppingisthatchoiceofapplicationsthatshouldbedegraded(cid:12)rstcanbecustomized.
`ScenariofourinFigureshowstheresultsforasimple\timesharing"policy,whereeveryfew
`secondsthedelegateswitchesthestreamthathasBframesdropped.Thisimprovesperformance
`byanother -%.Policiesthatdi(cid:11)erentiatebetween(cid:13)owscouldsimilarlybeimplemented.
`.DynamiccontrolofMJPEGvideoencoding
`Analternativeapproachtoselectiveframedroppinginvideoapplicationstodealwithcongestion
`istouseavideotranscodertocompress,orchangethelevelofcompression,ofthevideostream
`dependingontheavailablebandwidth.Weusebothcontrolanddatadelegatesinthisexample
`toillustratehowdelegatescancontrolcompressionlevelsforvideoqualityoptimizationvia(cid:13)ow
`monitoring,(cid:13)owredirectingandinter-delegatecommunication.Acontroldelegateissetuponthe
`routerbeforethebottlenecklinkontherouteofthevideoapplication.Thecontroldelegatealters
`theoriginalroutethatthevideostreamwilltakeby(cid:12)rstredirectingthe(cid:13)owtoadatadelegate
`whichresidesonacomputeservernexttotherouter.Thedatadelegatefunctionsasatranscoder
`inthatittakesinrawvideoandgeneratesMJPEGframesusingdi(cid:11)erentcompressionlevels.The
`MJPEGframesarethenfedbacktothebottleneckrouter,andwillonlythenbeforwardedtothe
`originallyintendedreceiver.Thecontroldelegatemonitorsthebottlenecklink'scongestionstatus.
`Whenfacingcongestion,thecontroldelegatedirectsthedatadelegatetouseahighercompression
`levelforlessbandwidthusage.Atothertimes,whenthecontroldelegateseesabundantbandwidth
`onthebottlenecklink,itcanpromptthedatadelegatetodeployalowercompressionlevelfor
`bettervideoquality.Thisallowsthevideo(cid:13)owtoopportunisticallytakeadvantageofavailable
`bandwidth.
`Intheexperiment,anapplicationconsistingoftwoMJPEGvideostreamsandtwobursty
`datastreamscompetefornetworkbandwidthwithotherusers,modeledasanunconstrainedUDP
`stream.All(cid:13)owsaredirectedoverthe MbpsTimberline-Mauilink.Theapplicationhas%
`ofthebandwidth,forvideoandfordata;theremaining %bandwi