failingcloudlink

LAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformShanheYiCollegeofWilliamandMarysyi@cs.
wm.
comZijiangHaoCollegeofWilliamandMaryhebo@cs.
wm.
comQingyangZhangWayneStateUniversityAnhuiUniversity,Chinaqyzhang@wayne.
comanZhangWayneStateUniversityquan.
zhang@wayne.
comWeisongShiWayneStateUniversityweisong@wayne.
comnLiCollegeofWilliamandMaryliqun@cs.
wm.
comABSTRACTAlongthetrendpushingcomputationfromthenetworkcoretotheedgewherethemostofdataaregenerated,edgecomputinghasshownitspotentialinreducingresponsetime,loweringbandwidthusage,improvingenergyeciencyandsoon.
Atthesametime,low-latencyvideoanalyticsisbecomingmoreandmoreimportantforapplicationsinpublicsafety,counter-terrorism,self-drivingcars,VR/AR,etc.
Asthosetasksareeithercomputationintensiveorbandwidthhungry,edgecomputingtsinwellherewithitsabilitytoexiblyutilizecomputationandbandwidthfromandbetweeneachlayer.
Inthispaper,wepresentLAVEA,asystembuiltontopofanedgecomputingplatform,whichooadscomputationbetweenclientsandedgenodes,collaboratesnearbyedgenodes,toprovidelow-latencyvideoanalyticsatplacesclosertotheusers.
Wehaveutilizedanedge-rstdesignandformulatedanoptimizationprob-lemforooadingtaskselectionandprioritizedooadingrequestsreceivedattheedgenodetominimizetheresponsetime.
Incaseofasaturatingworkloadonthefrontedgenode,wehavedesignedandcomparedvarioustaskplacementschemesthataretailedforinter-edgecollaboration.
Wehaveimplementedandevaluatedoursystem.
Ourresultsrevealthattheclient-edgecongurationhasaspeeduprangingfrom1.
3xto4x(1.
2xto1.
7x)againstrunninginlocal(client-cloudconguration).
eproposedshortestsched-ulinglatencyrstschemeoutputsthebestoveralltaskplacementperformanceforinter-edgecollaboration.
CCSCONCEPTSNetworks→Cloudcomputing;Computingmethodologies→Objectrecognition;Sowareanditsengineering→Publish-subscribe/event-basedarchitectures;KEYWORDScomputationooading,edgecomputingPermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationontherstpage.
CopyrightsforcomponentsofthisworkownedbyothersthanACMmustbehonored.
Abstractingwithcreditispermied.
Tocopyotherwise,orrepublish,topostonserversortoredistributetolists,requirespriorspecicpermissionand/orafee.
Requestpermissionsfrompermissions@acm.
org.
SEC'17,SanJose/SiliconValley,CA,USA2017ACM.
978-1-4503-5087-7/17/10.
.
.
$15.
00DOI:10.
1145/3132211.
3134459ACMReferenceformat:ShanheYi,ZijiangHao,QingyangZhang,anZhang,WeisongShi,andnLi.
2017.
LAVEA:Latency-awareVideoAnalyticsonEdgeCom-putingPlatform.
InProceedingsofSEC'17,SanJose/SiliconValley,CA,USA,October12–14,2017,13pages.
DOI:10.
1145/3132211.
31344591INTRODUCTIONEdgecomputing(alsotermedfogcomputing[4],cloudlets[28],MEC[24],etc.
)hasbroughtusbeeropportunitiestoachievetheultimategoalofaworldwithpervasivecomputation[28].
isnewcomputingparadigmisproposedtoovercometheinherentproblemsofcloudcomputingandprovidesupportstotheemergingInternetofings(IoT)[14,33,37].
Typically,whenusingthecloud,allthedatageneratedshallbeuploadedtotheclouddatacenterbeforeprocessing.
However,consideringnowadaysahugeamountofdataisbeingintensivelygeneratedattheedgeofthenetwork,transferringthedataatsuchscaletothedistantcloudforprocessingwilladdburdenstothenetworkandleadtounacceptableresponsetime,especiallyforlatency-sensitiveapplications.
Morespecically,asforedgecomputing,weaimtoprovideedgeanalytics,whichfocusesondataanalyticsatorneartheplaces(thenetworkedge)wheredataisgenerated[30].
Dataanalyticsdoneattheedgeofthenetworkhasmanybenetssuchasgatheringmoreclientsideinformation,cuingshorttheresponsetime,savingnetworkbandwidth,loweringthepeakworkloadtothecloud,andsoon.
Amongmanyedgeanalyticapplications,inthispaper,wefocusondeliveringvideoanalyticsattheedge.
eabilitytoprovidelowlatencyvideoanalyticsiscriticalforapplicationsintheeldsofpublicsafety,counter-terrorism,self-drivingcars,VR/AR,etc[32].
Invideoedgeanalyticapplications,weconsidertypicalclientde-vicessuchasmobilephones,body-worncamerasordashcamerasmountedonvehicles,webcamerasattollstationsorhighwaycheck-points,securitycamerasinpublicplaces,orevenvideocapturedbyUAVs[35].
Forexample,in"AmberAlert",oursystemcanau-tomateandspeedupthesearchingofobjectsofinterestbyvehiclerecognition,vehiclelicenseplaterecognitionandfacerecognitionutilizingvariouswebcamerasdeployedathighwayentrances,ordashcamerasorcamerasofsmartphonesmountedoncars.
Simplyuploadingallthecapturedvideoorredirectingvideofeedstothecloudcannotmeettherequirementoflatency-sensitiveapplications,becausethecomputervisionalgorithmsinvolvedinSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAS.
Yietal.
objecttracking,objectdetection,objectrecognition,faceandopti-calcharacterrecognition(OCR)areeithercomputationintensiveorbandwidthhungry.
Inaddressingtheseproblems,mobilecloudcom-puting(MCC)isproposedtorunheavytasksonresourcerichcloudnodetoimprovetheresponsetimeorenergycost.
istechniqueutilizesboththemobileandcloudforcomputation.
Anappropriatepartitionoftasksthatmakestrade-obetweenlocalandremoteexecutioncanspeedupthecomputationandpreservemobileen-ergyatthesametime[7,13,15,21,31].
However,therearestillconcernsofcloudaboutthelimitedbandwidth,theunpredictablelatency,andtheabruptserviceoutage.
Existingworkhasexploredaddingintermediateservers(cloudlets)betweenmobileclientandthecloud.
Cloudletisanearlyimplementationofthecloud-likeedgecomputingplatformwithvirtualmachine(VM)techniques.
eedgecomputingplatforminourworkhasadierentdesignontopoflightweightOS-levelvirtualizationwhichismodular–easytodeploy,manage,andscale.
ComparedtoVM,theOS-levelvirtualizationprovidesresourceisolationinamuchlowercost.
eadoptionofcontainertechniqueleadstoaserver-lessplatformwheretheendusercandeployandenableedgecomputingplatformonheterogeneousdeviceswithminimaleorts.
euserprograms(scriptsorexecutablebinaries)willbeencapsulatedincontainers,whichprovideresourceisolation,self-containedpackaging,any-wheredeploy,andeasy-to-congureclustering.
eenduseronlyneedstoregistereventsofinterestandprovidecorrespondinghan-dlerfunctionstooursystem,whichautomaticallyhandletheeventsbehindthescene.
Inthispaper,weareconsideringa3-tiermobile-edge-cloudde-ploymentandweputmostofoureortsintothemobile-edgesideandinter-edgesidedesign.
Todemonstratetheeectivenessofouredgecomputingplatform,wehavebuilttheLatency-AwareVideoEdgeAnalytics(LAVEA)system.
Wedividetheresponsetimemin-imizationproblemintothreesub-problems.
First,weselectclienttasksthatbenetfrombeingooadedtoedgenodeinreducingtimecost.
Weformulatedthisproblemasamathematicaloptimiza-tionproblemtochooseooadingtasksandallocatebandwidthamongclients.
Unlikeexistingworkinmobilecloudcomputing,wecannotmaketheassumptionthatedgenodeisaspowerfulascloudnodewhichcanprocessallthetasksinstantly.
erefore,weconsidertheincreasingresourcecontentionandresponsetimewhenmoreandmoretasksarerunningonedgenodebyaddinglatencyconstraintstotheoptimizationproblem.
Second,uponre-ceivingooadingtaskrequestsateachepoch,theedgenoderunsthesetasksinanordertominimizethemakespan.
However,theooadedtaskscannotbestartedwhenthecorrespondinginputsarenotready.
Toaddressthisproblem,weemployedaclassictwo-stagejobshopmodelandadaptedJohnson'srulewithtopologicalorderingconstraintinaheuristictoprioritizethetasks.
Last,weenableinter-edgecollaborationleveragingnearbyedgenodestore-ducetheoveralltaskcompletiontime.
Wehaveinvestigatedseveraltaskplacementschemesthataretailoredforinter-edgecollabo-ration.
endingsprovidedusinsightsthatleadtoanecientprediction-basedtaskplacementscheme.
Insummary,wemakethefollowingcontributions:Wehavedesignedanedgecomputingplatformbasedonaserver-lessarchitecture,whichisabletoprovideexi-blecomputationooadingtonearbyclientstospeedupcomputation-intensiveanddelay-sensitiveapplications.
Ourimplementationislightweight-virtualized,event-based,modular,andeasytodeployandmanageoneitheredgeorcloudnodes.
Wehaveformulatedanoptimizationproblemforooad-ingtaskselectionandprioritizedooadingrequeststominimizetheresponsetime.
etaskselectionproblemco-optimizestheooadingdecisionandbandwidthalloca-tion,andisconstrainedbythelatencyrequirement,whichcanbetunedtoadapttotheworkloadonedgenodeforooading.
etaskprioritizingismodeledasatwo-stagejobshopproblemandaheuristicisproposedwiththetopologicalorderingconstraint.
Wehaveevaluatedseveraltaskplacementschemesforinter-edgecollaborationandproposedapredication-basedmethodwhichecientlyestimatestheresponsetime.
2BACKGROUNDANDMOTIVATIONInthissection,webrieyintroducethebackgroundofedgecom-putingandrelevanttechniques,presentourobservationsfrompreliminarymeasurements,anddiscussthescenariosthatmotivateus.
Figure1:Anoverviewofedgecomputingenvironment2.
1EdgeComputingNetworkInthepaper,weconsideranedgecomputingnetworkasshowninFigure1,inwhichwefocusontwotypesofnodes,theclientnode(inthispaper,wecallitclientforshort)andtheedgeservernode(inthispaper,wecallitedge,edgenode,oredgeserverforshort).
Weassumethatclientsareone-hopawayfromedgeserverviawireorwirelesslinks.
Whenaclientconnectstotheedgenode,weimplicitlyindicatethattheclientwillrstconnecttothecorrespondaccesspoints(APs)usingcableorwirelessandthenutilizetheservicesprovidedbytheco-locatededgenode.
InaLAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAsparseedgenodedeployment,aclientwillonlyconnecttooneoftheavailableedgenodesnearbyatcertainlocation.
Whileinadensedeployment,aclientmayhavemultiplechoicesonselectingthemultipleedgeserversforservices.
Implicitly,weassumethatthereisaremotecloudnodewhichcanbereachedviathewideareanetwork(WAN).
Tounderstandthefactorsthatimpactthefeasibilityofrealiz-ingpracticaledgecomputingsystems,wehaveperformedseveralpreliminarymeasurementsonexistingnetworkandshowntheresultsinFig.
2andFig.
3.
Intheseexperiments,wemeasuredthelatencyandbandwidthofcombinationsbetweenclientsnodeswithdierentnetworkinterfacesconnectingtoedge(orcloud)nodes.
Basedonthemeasurementsofbandwidth,allclientshavebenetsinutilizingawire-connectedoradvanced-wireless(802.
11ac5Ghz)edgecomputingnode.
Intermsoflatency,wire-connectededgenodesisthebestwhilethe5Ghzwirelessedgecomputingnodeshavelargermeansandvariancesinlatencycomparedtothecloudnodeintheclosestregionduetotheintrinsicnatureofwirelesschannels.
erefore,inthispaper,wepragmaticallyassumethatedgenodesareconnectedtoAPsviacablestodeliverserviceswithbeerlatencyandbandwidththanthecloud.
erefore,insuchasetup,thecloudnodecanbeconsideredasabackupcomputingnode,whichwillbeutilizedonlywhentheedgenodeissaturatedandexperiencesalongresponsetime.
Figure2:Roundtriptimebetweenclientandedge/cloud.
2.
2ServerlessArchitectureServerlessarchitectureorFunctionasaService(FaaS),suchasAWSLambda,GoogleCloudFunction,AzureFunctions,isanagilesolutionfordevelopertobuildcloudcomputingserviceswithouttheheavyliingofmanagingcloudinstances.
TouseAWSLambdaasanexample,AWSLambdaisaevent-based,micro-serviceframe-work,inwhichauser-suppliedLambdafunctionastheapplicationlogicwillbeexecutedinresponsetocorrespondingevent.
eAWScloudwilltakecareoftheprovisioningandresourcemanagementforrunningLambdafunctions.
AtthersttimeaLambdafunctioniscreated,acontainerwillbebuiltandlaunchedbasedonthecon-gurationsprovided.
Eachcontainerwillalsobeprovidedasmalldiskspaceastransientcacheduringmultipleinvocations.
AWShasitsownwaytorunLambdafunctionswitheitherreusinganFigure3:Bandwidthbetweenclientandedge/cloud.
existingcontainerorcreatinganewone.
Recently,thereisAWSLambda@Edge[1],thatallowsusingserverlessfunctionsattheAWSedgelocationinresponsetoCDNeventtoapplymoderatecomputations.
Westronglyadvocatetheadoptionofserverlessar-chitectureattheedgecomputinglayers,asserverlessarchitecturenaturallysolvestwoimportantproblemsforedgecomputing:1)serverlessprogrammingmodelgreatlyreducestheburdenonusersordevelopersindeveloping,deployingandmanagingedgeappli-cations,asthereisnoneedtounderstandthecomplexunderlyingprocedurestoruntheapplicationsorheavyliingofdistributedsys-temmanagement;2)thefunctionsareexibletorunoneitheredgeorcloud,whichlowersthebarrierofedge-cloudinter-operatabilityandfederation.
Recentworkshaveshownthepotentialsofsucharchitectureinlowlatencyvideoprocessingtasks[11]anddis-tributedcomputingtasks[20],andtherehavebeenresearcheortsofincorporatingserverlessarchitectureinedgecomputing[8].
2.
3VideoEdgeAnalyticsforPublicSafetyVideosurveillanceisofgreatimportanceforpublicsafety.
Besidesthe"AmberAlert"example,therearemanyotherapplicationsinthiseld.
Forexample,securecamerasdeployedatpublicplaces(e.
g.
theairport)canquicklyspotunaendedbags[42],policewithbody-worncamerascanidentifysuspectsandsuspiciousvehi-clesduringapproaching,andsoon.
Becausethosescenariosareurgentandcritical,theapplicationsneedtoprovidethequickestresponseswithbesteorts.
However,mosttasksinvideoanalyticsareundoubtedlycomputationallyintensive[26].
WhilerunningonresourceconstrainedmobileclientsorIoTdevicesdirectly,thelatencyincomputation,baerydrain(ifbaery-powered),orevenheatdissipationwilleventuallyruintheuserexperience,failingtoachievetheperformancegoalsoftheapplications.
Ifrunningoncloudnodes,transferringlargevolumeofmultimediadatawillincurunacceptabletransmissionlatencyandadditionalbandwidthcost.
Beingproposedasadedicatedsolution,thedeploymentofedgecomputingplatformenablesthequickestresponsestothesevideoanalyticstaskswhichrequirebothlowlatencyandhighbandwidth.
Inthispaper,wemainlyfocusonbuildingvideoedgeanalyticsplatformandwedemonstrateourplatformusingtheapplicationofAutomatedLicensePlateRecognition(ALPR).
Eventhoughweintegratespecicapplication,ouredgeplatformisageneraldesignSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAS.
Yietal.
andcanbeextendedforotherapplicationwithlilemodications.
AnALPRsystemusuallyhasfourstages:1)imageacquisition,2)licenseplateextraction,3)licenseplateanalysis,and4)characterrecognition[2,10].
Eachofthestagesinvolvesvariouscomputervision,paernrecognition,andmachinelearningalgorithms.
Mi-gratingtheexecutionofsomealgorithmstopowerfuledge/cloudnodecansignicantlyreducetheresponsetime[34].
However,of-oadedtasksrequireintermediatedata,applicationstatevariables,andcorrespondingcongurationstobeuploaded.
Someofthealgo-rithmsproducelargeamountofintermediatedatawilladddelaytothewholeprocessingtimeifooadedtoremotecloud.
WebelievethatacarefullydesignededgecomputingplatformwillassistALPRsystemtoexpandonmoreresource-constraineddevicesatmorelocationsandprovidebeerresponsetimeatthesametime.
3LAVEASYSTEMDESIGNInthissection,wepresentoursystemdesign.
First,wewilldiscussourdesigngoals.
en,wewilloverviewoursystemdesignandintroduceseveralimportantedgecomputingservices.
3.
1DesignGoalsLatency.
eabilitytoprovidelowlatencyservicesisrecognizedasoneoftheessentialrequirementsofedgecomputingsystemdesign.
Flexibility.
Edgecomputingsystemshouldbeabletoexiblyutilizethehierarchicalresourcesfromclientnodes,nearbyedgenodesandremotecloudnodes.
Edge-rst.
Byedge-rst,wemeanthattheedgecomput-ingplatformistherstchoiceofourcomputationooad-ingtarget.
3.
2SystemOverviewLAVEAisintrinsicallyanedgecomputingplatform,whichsupportslow-latencyvideoprocessing.
emaincomponentsareedgecom-putingnodeandedgeclient.
Wheneveraclientisrunningtasksandthenearbyedgecomputingnodeisavailable,ataskcanbedecidedtoruneitherlocallyorremotely.
WepresentthearchitectureofouredgecomputingplatforminFigure4.
3.
2.
1EdgeComputingNode.
InLAVEA,theedgecomputingnodeprovidesedgecomputingservicestothemobiledevicesnearby.
eedgecomputingnodeaachedtothesameaccesspointorbasestationasclientsiscalledtheedge-front.
Bydeployingedgecom-putingnodewithaccesspointorbasestation,weensurethatedgecomputingservicecanbeasubiquitousasInternetaccess.
Multipleedgecomputingnodescancollaborateandtheedge-frontwillal-waysserveasthemasterandbeinchargeofthecoordinationwithotheredgenodesandcloudnodes.
AsshowninFigure4,weusethelight-weightvirtualizationtechniquetoprovideresourceallo-cationandisolationtodierentclients.
AnyclientcansubmittaskstotheplatformviaclientAPIs.
eplatformwillberesponsibleforshapingworkload,managingqueuepriorities,andschedulingtasks.
osefunctionsareimplementedviainternalAPIsprovidedbymultiplemicro-servicessuchasqueueingservice,schedulingservice,datastoreservice,etc.
Wewillintroduceseveralimportantserviceslaterinthissection.
3.
2.
2EdgeClient.
Sincemostedgeclientsareeitherresourceconstraineddevicesorneedtoaccommodaterequestsfromalargenumberofclients,anedgeclientusuallyrunslightweightdatapro-cessingtaskslocallyandooadsheavytaskstotheedgecomputingnodenearby.
InLAVEA,theedgeclienthasathinclientdesign,tomakesurealltheclientscanrunitwithoutintroducingtoomuchoverhead.
Forlow-enddevices,thereisonlyoneworkertomakeprogressontheassignedjob.
emostimportantpartofclientnodedesignistheprolerandtheooadingcontroller,actingasparticipantsinthecorrespondingprolerserviceandooadingservice.
Withprolerandooadingcontroller,aclientcanprovideooadinginformationtotheedge-frontnodeandfulllooadingdecisionreceived.
3.
3EdgeComputingServices3.
3.
1ProfilerService.
Similarto[7,21,31],oursystemusesaprolertocollecttaskperformanceinformationonvariousdevices,sinceitisdiculttoderiveananalyticmodeltoaccuratelycapturethebehaviorofthewholesystem.
However,wehavefoundthattheexecutionofvideoprocesstasksisrelativelystable(wheninputandalgorithmiccongurationsaregiven)andaprolercanbeusedtocollectrelevantmetrics.
erefore,weaddaprolingphasetothedeploymentofeverynewtypeofclientdevicesandedgedevices.
eprolerwillexecuteinstrumentedtasksmultipletimeswithdierentinputsandcongurationsonthedeviceandmeasuremetricsincludingbutnotlimitedtoexecutiontime,input/outputdatasize,etc.
etime-stampedlogswillbegatheredtobuildthetaskexecutiongraphforspecictasks,inputs,congurations,anddevices.
eprolerservicewillcollectthoseinformation,onwhichLAVEAreliesforooadingdecisions.
3.
3.
2MonitoringService.
Unlikeprolerservicewhichgath-erspre-run-timeexecutioninformationonpre-denedinputsandcongurations,themonitoringserviceisusedtocontinuouslymon-itorandcollectrun-timeinformationsuchasthenetwork,systemload,etc.
,fromnotonlytheclientsbutalsonearbyedgenodes.
Monitoringthenetworkbetweenclientandedge-frontisneces-sarysincemostedgeclientsareconnectedtoedge-frontserverviawirelesslink.
econditionofwirelesslinkischangingfromtimetotime.
erefore,weneedtoconstantlymonitorthewirelesslink,toestimatethebandwidthandthelatency.
Monitoringsystemloadontheedgeclientprovidesexibleworkloadshapingandtaskooadingfromclienttotheedge.
isinformationisalsobroadcastedamongnearbyedgenodes.
Whenanedge-frontnodeissaturatedorunstable,sometaskswillbeassignedtonearbyedgenodesaccordingtothesystemload,thenetworkbandwidth,andnetworkdelaybetweenedgenodesaslongasthereisstillbenetcomparedtoassigningtaskstocloudnode.
3.
3.
3OloadingService.
eooadingcontrollerwilltracktasksrunninglocallyattheclient,andexchangeinformationwiththeooadingservicerunningontheedge-frontserver.
evari-ablesgatheredinprolerandmonitoringserviceswillbeusedasinputstotheooadingdecisionproblemwhichisformulatedasanoptimizationproblemtominimizetheresponsetime.
Everytimewhenanewclientregistersitselftotheooadingservices,aertheedge-frontnodecollectsenoughprerequisiteinformationandLAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAFigure4:earchitectureofedgecomputingplatformstatistics,theoptimizationproblemissolvedagainandtheupdatedooadingdecisionswillbesenttoalltheclients.
Periodically,theooadingservicealsosolvestheoptimizationproblem,andupdatesooadingdecisionswithitsclients.
4EDGE-FRONTOFFLOADINGInthissection,weconsiderselectingtaskstorunontheedgeasacomputationooadingproblem.
Traditionalooadingproblemsareaboutooadingschemesbetweenclientsandremotepowerfulcloudservers.
Inliterature[7,21,31],thesesystemmodelsusuallyassumethetaskwillbeinstantlynishedremotelyoncethetaskisooadedtotheserver.
However,wearguethatthisassumptionwillnotholdinedgecomputingenvironmentasweneedtoconsiderthevariousdelaysattheserversideespeciallywhenlotsofclientsaresendingooadingrequests.
Wecallitedge-frontcomputationooadingfromtheperspectiveofclient:Taskswillbeonlybyooadedfromclienttothenearestedgenode,whichwecalltheedgefront.
eunderlyingschedulingandprocessingisagnostictoclients.
Whenamobilenodeisdisconnectedfromanyedgenodeorevencloudnode,itwillresorttolocalexecutionofallthetasks.
Weassumethatedgenodeiswire-connectedtotheaccesspoint,whichindicatesthattheout-goingtraccangothroughedgenodewithnoadditionalcost.
eonlydierencebetweenooadingtasktoedgenodeandcloudnode,isthatthetaskrunningonedgenodemayexperienceresourcecontentionandschedulingdelaywhileweassumetaskooadedtocloudnodewillgetenoughresourceandbescheduledtorunimmediately.
Inlightworkloadcase,ifthereisanyresponsetimereductionwhenthistaskisooadedtocloud,thenweknowthatthereisdenitelybenetwhenthistaskisooadedtotheedge.
ereasonsare1)anedgeserverisasresponsiveastheserverintheclouddatacenter,2)runningataskonedgeserverexperiencesshorterdatatransmissiondelayasclient-edgelinkhasmuchlargerbandwidththanedge-cloudlinkwhichisusuallylimitedandimbalancedbytheInternetserviceproviders(ISPs).
erefore,inthissection,wefocusonthetaskooadingonlybetweenclientandedgeserver,andwewilldiscussintegratingnearbyedgenodesfortheheavyworkloadscenariointhenextsection.
4.
1TaskOloadingSystemModelandProblemFormulationroughoutthepaper,wecallarunninginstanceoftheapplicationajob,whichconsistsasetoftasks.
ejobistheunitofworkthatusersubmitstooursystemwhilethetaskistheunitofworkforoursystemtomakeschedulingandoptimizationdecisions.
esetasksfromeachapplicationwillbequeuedandprocessedeitherlocallyorremotely.
Byremotely,wemeanrunthetaskonanedgenode.
Inouredgeapplicationscenario,allclientsarerunninginstancesofapplicationsprocessingsamekindofjobs.
However,oursystemcanbeeasilyextendedtosupportheterogeneousapplications.
InourALPRapplication,eachtaskisusuallyacomputervisionalgorithm.
Forexample,WehaveanalyzedanopensourceALPRSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAS.
Yietal.
projectcalledOpenALPR[22]andillustrateitstaskgraphinFig.
5.
Wechoosetoworkonthegranularityoftasksincethesetasksaremodularizedandcanbeexiblypipelinedwithtunedparameterstomaketrade-obetweenquickprocessingandaccurateresult.
Figure5:etaskgraphofOpenALPR.
enweconsiderthereareNclientsandonlyoneedgeserverconnectedasshowninFig.
1.
isedgeservercouldbeasingleserveroraclusterofservers.
Eachclienti,i∈[1,N],willprocesstheupcomingjobuponrequest,e.
g.
recognizingthelicenseplatesinvideostreams.
Weexpectthatthejobconsistsheavycomputationtaskscouldbenetfromooadingsometaskstotheedgeserver.
Withoutlossofgenerality,weuseagraphoftasktorepresentthecomplextaskdependenciesinsideajob,whichisessentiallysimilartothemethodcallgraphin[7],butinamorecoarsegranularity.
Foracertainkindofjob,westartwithitsdirectedacyclicgraph(DAG),G=(V,E),whichgivesthetaskexecutionsequence.
Eachvertex∈Vweightisthecomputationormemorycostofatask(c),whileeachedgee=(u,),u,∈V,e∈Eweightrepresentsthedatasizeofintermediateresults(du).
us,ourooadingproblemcanbetakenasagraphpartitionproblem,inwhichweneedtoassignadirectedgraphoftaskstodierentcomputingnodes(local,edge,orcloud),withthepurposetominimizecertaincost.
Inthispaper,weprimarilytrytominimizethejobnishtime.
eremoteresponsetimeincludesthecommunicationdelay,thenetworktransmissiondelayofsendingdatatotheedgeserver,andtheexecutiontimeonthatserver.
WeuseanindicatorI,i∈{0,1}forallinVandforalli∈[1,N].
IfI,i=1,thenthetaskatclientiwillrunlocally,otherwise,itwillrunontheremoteedgeserver.
Forthosetasksrunninglocally,thetotalexecutiontimeforclientiisasummation:Tlocali=∈VI,ic/pi(1)wherepiistheprocessorspeedofclienti.
Similarly,weuseTlocali=∈V(1I,i)c/pi(2)torepresenttheexecutiontimeofrunningtheooadedtaskslocallyinstead.
Inthenetwork,whenthereisanooadingdecision,theclientneedtosendtheintermediatedata(outputsofprevioustask,applicationstatus,congurations,etc)totheedgeserverinordertocontinuethecomputing.
enetworkdelayismodeledasTneti=(u,)∈E|Iu,iI,i|du/ri+βi(3)whereriistheconnectionrateassignedforthisclientconnectingtotheedgeserverandβiisthecommunicationlatencywhichcanbeestimatedusingroundtriptimebetweentheclientiandtheedgeserver.
Foreachclient,theremoteexecutiontimeisTremotei=∈V(1I,i)(c/p0)(4)wherep0istheprocessorspeedoftheedgeserver.
enourooadingtaskselectionproblemcanbeformulatedasminIi,riNi=1(Tlocali+Tneti+Tremotei)(5)eooadingtaskselectionisrepresentedbytheindicatormatrixI.
isoptimizationproblemissubjecttothefollowingconstraints:etotalbandwidths.
t.
Ni=1ri≤R(6)Likeexistingwork,werestrictthedataowtoavoidping-pongeectinwhichintermediatedataistransmiedbackandforthbetweenclientandedgeserver.
s.
t.
I,i≤Iu,i,e(u,)∈E,i∈[1,N](7)Unlikeexistingooadingframeworksformobilecloudcomputing,wetaketheresourcecontentionorschedulingdelayattheedgesideintoconsiderationbyaddinganend-to-enddelayconstraint.
s.
t.
Tlocali(Tneti+Tremotei)>τ,i∈[1,N](8)whereτcanbetunedtoavoidselectingborderlinetasksthatifooadedwillgetnogainduetotheresourcecon-tentionorschedulingdelayattheedge.
4.
2OptimizationSolvereproposedoptimizationisamixedintegernon-linearprogram-mingproblem(MINLP),wheretheintegervariablestandsfortheooadingdecisionandthecontinuousvariablestandsforthecon-nectionrate.
Tosolvethisoptimizationproblem,westartfromLAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USArelaxingtheintegerconstraintsandsolvethenon-linearprogram-mingversionoftheproblemusingSequentialadraticProgram-mingmethod,aconstrainednonlinearoptimizationmethod.
issolutionisoptimalwithoutconsideringtheintegerconstraints.
Startingfromthisoptimalsolution,weoptionallyemploybranchandbound(B&B)methodtosearchfortheoptimalintegersolutionorsimplydoanexhaustivesearchwhenthenumberofclientsandthenumberoftasksofeachjobaresmall.
4.
3PrioritizingEdgeTaskeueeooadingstrategyproducedbythetaskselectionoptimizesthe"ow"timeofeachtypeofjob.
Ateachtimeepochduringtheruntime,theedge-frontnodereceivesalargenumberofooadedtasksfromtheclients.
Originally,wefollowtherstcomerstserveruletoaccommodatealltheclientrequests.
Foreachrequestattheheadofthetaskqueue,theedge-frontserverrstchecksiftheinputorintermediatedata(e.
g.
imagesorvideos)isavailableattheedge,otherwisetheserverwaits.
isschemeiseasytoimplementbutsubstantialcomputationiswastedifthenetworkIOisbusywithalargesizeleandthereisnotaskthatisreadyforprocessing.
erefore,weimprovethetaskschedulingwithataskqueueprioritizertomaintainatasksequencewhichmini-mizesthemakespanforthetaskschedulingofallooadingtaskrequestsreceivedatacertaintimeepoch.
Sincetheedgenodecanexecutethetaskonlywhentheinputdatahasbeenfullyreceivedorthedependedtaskshavenishedexecution,weconsiderthatanooadedtaskhastogothroughtwostages:therststageistheretrievalofinputorintermediatedataandstatevariables;thesecondstageistheexecutionofthetask.
WestudyourschedulingproblemusingtheowjobshopmodelandapplytheJohnson'srule[19].
isschemeisoptimalandthemakespanisminimized,whenthenumberofstagesistwo.
Nev-ertheless,thismodelonlytsinthecasethatallsubmiedjobrequestsareindependentandhavenopriorities.
Whenconsideringtaskdependencies,asuccessorcanonlystartaeritspredecessornishes.
Byenforcingthetopologicalorderingconstraints,theproblemcanbesolvedoptimallyusingtheB&Bmethod[5].
How-ever,thissolutionhardlyscalesagainstthenumberoftasks.
Inthiscase,weadaptthemethodin[3],i.
e.
,groupingtaskswithdependenciesandexecutingalltasksinagroupsequentially.
ebasicideaisapplyingJohnson'sruleintwolevels.
erstlevelistodecidethesequenceoftaskswithineachgroup.
edier-enceinourproblemisthatweneedtodecidethebestsequenceamongallvalidtopologicalorderings.
eboomlevelisajobshopschedulingproblemintermsofgroupedjobs(i.
e.
,agroupoftaskswithdependenciesintopologicalordering),inwhichwecanutilizeJohnson'sruledirectly.
4.
4WorkloadOptimizerIftheworkloadisoverwhelmingandtheedge-frontserverissatu-rated,thetaskqueuewillbeunstableandtheresponsetimewillbeaccumulatedindenitely.
ereareseveralmeasuresLAVEAcantaketoaddressthisproblem.
First,oursystemcanadjusttheim-age/videoresolutionviaclient-sidecongurations,whichmakesawelltrade-obetweenspeedandaccuracy.
Second,byconstrainingthetaskooadingproblem,oursystemcanrestrainmorecompu-tationtasksattheclientside.
ird,iftherearenearbyedgenodeswhicharefavoredintermsoflatency,bandwidth,andcomputation,oursystemcanfurtherooadtaskstonearbyedgenodes.
Wehaveinvestigatedthiscasewithperformanceimprovementconsidera-tionsinSection5.
Last,oursystemcanalwaysredirecttaskstotheremotecloud,justliketaskooadinginMCC.
5INTER-EDGECOLLABORATIONInthissection,weimproveouredge-rstdesignbytakingthecasewhentheincomingworkloadsaturatesouredge-frontnodeintoconsideration.
Wewillrstdiscussourmotivationofprovidingsuchoptionandlistthecorrespondingchallenges.
enwewillintroduceseveralcollaborationschemeswehaveproposedandinvestigated.
5.
1MotivationandChallengeseresourcesofedgecomputingnodearemuchricherthanclientnodesbutarerelativelylimitedcomparedtocloudnodes.
Whileservinganincreasingnumberofclientnodesnearby,theedge-frontnodewillbeeventuallyoverloadedandbecomenon-responsivetonewrequests.
Asabaseline,wecanoptionallychoosetoooadfur-therrequeststotheremotecloud.
Weassumethattheremotecloudhasunlimitedresourcesandiscapabletohandlealltherequests.
However,runningtasksremotelyinthecloud,theapplicationneedtobearwithunpredictablelatencyandlimitedbandwidth,whichisnotthebestchoiceespeciallywhenthereareothernearbyedgenodesthatcanaccommodatethosetasks.
Weassumethatundertheconditionwhenallavailableedgenodesnearbyareexhausted,themobile-edge-cloudcomputingparadigmwillsimplyfallbacktothemobilecloudcomputingparadigm.
efallbackdesignisnotinthescopeofthispaper.
Inthispaper,wemainlyinvestigatetheinter-edgecollaborationwiththeprimarypurposetoalleviatetheburdenonedge-frontnode.
Whentheedge-frontnodeissaturatedwithrequests,itcancollaboratewithnearbyedgenodesbyplacingsometaskstothesenot-so-busyedgenodes,suchthatallthetaskscangetscheduledinareasonabletime.
isisslightlydierentfrombalancingtheworkloadamongtheedgenodesandtheedge-frontnode,inthatthegoalofinter-edgecollaborationistobeerservetheclientnodeswithsubmiedrequests,ratherthansimplymakingtheworkloadbalanced.
Forexample,anedge-frontnodethatisnotoverloadeddoesnotneedtoplaceanytaskstothenearbyedgenodes,evenwhentheyareidle.
echallengesofinter-edgecollaborationaretwo-fold:1)weneedtodesignaproperinter-edgetaskplacementschemethatfulllsourgoalofreducingtheworkloadontheedge-frontnodewhileooadingproperamountofworkloadtothequaliededgenodes;2)thetaskplacementschemeshouldbelightweight,scalable,andeasy-to-implement.
5.
2Inter-EdgeTaskPlacementSchemesWehaveinvestigatedthreetaskplacementschemesforinter-edgecollaboration.
ShortestTransmissionTimeFirst(STTF)ShortesteueLengthFirst(SQLF)SEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAS.
Yietal.
ShortestSchedulingLatencyFirst(SSLF)eSTTFtaskplacementschemetendstoplacetasksontheedgenodethathastheshortestestimatedlatencyfortheedge-frontnodetotransferthetasks.
eedge-frontnodemaintainsatabletorecordthelatencyoftransmiingdatatoeachavailableedgenode.
eperiodicalre-calibrationisnecessarybecausethenetworkconditionbetweentheedge-frontnodeandotheredgenodesmayvaryfromtimetotime.
eSQLFtaskplacementscheme,ontheotherhand,tendstotransfertasksfromtheedge-frontnodetotheedgenodewhichhastheleastnumberoftasksqueueduponthetimeofquery.
Whentheedge-frontnodeissaturatedwithrequests,itwillrstqueryalltheavailableedgenodesabouttheircurrenttaskqueuelength,andthentransfertaskstotheedgenodethathastheshortestvaluereported.
eSSLFtaskplacementschemetendstotransmittasksfromtheedge-frontnodetotheedgenodethatispredictedtohavetheshort-estresponsetime.
eresponsetimeisthetimeintervalbetweenthetimewhentheedge-frontnodesubmitsatasktoanavailableedgenodeandthetimewhenitreceivestheresultofthetaskfromthatedgenode.
UnliketheSQLFtaskplacementscheme,theedge-frontnodekeepsqueryingtheedgenodesaboutthequeuelength,whichmayhasperformanceissuewhenthenumberofnodesscalesupandresultsinalargevolumeofqueries.
Wehavedesignedanovelmethodfortheedge-frontnodetomeasuretheschedulinglatencyeciently.
Duringthemeasurementphasebeforeedge-frontnodechoosestaskplacementtarget,edge-frontnodesendsarequestmessagetoeachavailableedgenode,whichappendsaspecialtasktothetailofthetaskqueue.
Whenthespecialtaskisexecuted,theedgenodesimplysendsaresponsemessagetotheedge-frontnode.
eedge-frontnodereceivestheresponsemessageandrecordstheresponsetime.
Periodically,theedge-frontnodemaintainsaseriesofresponsetimesforeachavailableedgenode.
Whentheedge-frontnodeissaturated,itwillstarttoreassigntaskstotheedgenodehavingtheshortestresponsetime.
UnliketheSTTFandSQLFtaskassignmentschemes,whichchoosethetargetedgenodebasedonthecurrentormostrecentmeasurements,theSSLFschemepredictsthecurrentresponsetimeforeachedgenodebyapplyingregressionanalysistotheresponsetimeseriesrecordedsofar.
ereasonisthattheedgenodesarealsoreceivingtaskrequestsfromclientnodes,andtheirlocalworkloadmayvaryfromtimetotime,sothemostrecentresponsetimecannotserveasagoodpredictorofthecurrentresponsetimefortheedgenodes.
Asthelocalworkloadintherealworldoneachedgenodeusuallyfollowscertainpaernortrend,applyingregressionanalysistotherecordedresponsetimesisagoodwaytoestimatethecurrentresponsetime.
Tothisend,werecordedmeasurementsofresponsetimesfromeachedgenode,andooadstaskstotheedgenodethatispredictedtohavetheleastcurrentresponsetime.
Oncetheedge-frontnodestartstoplacetasktoacertainedgenode,theestimationwillbeupdatedusingpiggybackingoftheredirectedtasks,whichlowerstheoverheadofmeasuring.
Eachofthetaskplacementschemesdescribedabovehassomeadvantagesanddisadvantages.
Forinstance,theSTTFschemecanquicklyreducetheworkloadontheedge-frontnode.
Butthereisachancethattasksmaybeplacedtoanedgenodewhichalreadyhasintensiveworkload,asSTTFschemegathersnoinformationoftheworkloadonthetarget.
eSQLFschemeworkswellwhenthenetworklatencyandbandwidtharestableamongalltheavailableedgenodes.
Whenthenetworkoverheadsarehighlyvariant,thisschemefailstofactorthenetworkconditionandalwayschoosesedgenodewiththelowestworkload.
Whenanintensiveworkloadisplacedunderahighnetworkoverhead,thisschemepotentiallydeterioratestheperformanceasitneedstomeasuretheworkloadfrequently.
eSSLFtaskplacementschemeestimatestheresponsetimeofeachedgenodebyfollowingthetask-ooadingprocess,andtheresponsetimeisagoodindicatorofwhichedgenodeshouldbechosenasthetargetoftaskplacementintermsoftheworkloadandnetworkoverhead.
eSSLFschemeisawelltrade-obetweenprevioustwoschemes.
However,theregressionanalysismayintro-ducealargeerrortothepredictedresponsetimeifinappropriatemodelsareselected.
Webelievethatthedecisionofwhichtaskplacementschemeshouldbeemployedforachievinggoodsystemperformanceshouldalwaysgiveproperconsiderationsonthework-loadandnetworkconditions.
Weevaluatedthosethreeschemesthroughacasestudyinthenextsection.
6SYSTEMIMPLEMENTATIONANDPERFORMANCEEVALUATIONInthissection,werstbrieftheimplementationdetailsofbuildingoursystem.
Next,weintroduceourevaluationsetupandpresentevaluationresults.
6.
1ImplementationDetailsOurimplementationaimsataserverlessedgecomputingarchitec-ture.
AsshowninsystemarchitectureofFig.
4,ourimplementationisbasedondockercontainerforthebenetsofquickdeploymentandeasymanagement.
Everycomponenthasbeendockerizedanditsdeploymentisgreatlysimpliedviadistributingpre-builtimages.
ecreationanddestructionofdockerinstancesismuchfasterthanthatofVMinstances.
InspiredbytheIBMOpenWhisk[18],eachworkercontainercontainsanactionproxy,whichusesPythontorunanyscriptsorcompileandexecuteanybinaryexecutable.
eworkercontainercommunicateswithothersusingamessagequeue,asalltheinputs/outputswillbejsonied.
However,wedon'tjsoniedimage/videoanduseitspathreferenceinsharedstorage.
etaskqueueisimplementedusingRedisasitisinmemoryandhasverygoodperformance.
eenduseronlyneedsto1)deployouredgecomputingplatformonheterogeneousdeviceswithjustaclick,2)denetheeventofinterestsusingaprovidedAPI,and3)provideafunction(scriptsorbinaryexecutable)toprocesssuchevent.
efunctionwehaveimplementedutilizestheopensourceprojectOpenALPR[22]asthetaskpayloadforworkers.
6.
2EvaluationSetup6.
2.
1Testbed.
Wehavebuiltatestbedconsistingoffouredgecomputingnodes.
Oneoftheedgenodesistheedge-frontnode,whichisdirectlyconnectedtoawirelessrouterusingacable.
Otherthreenodesaresetasnearbyedgecomputingnodesfortheevalua-tionofinter-edgecollaboration.
esefourmachineshavethesamehardwarespecications.
eyallhaveaquad-coreCPUand4GBmainmemory.
ethreenearbyedgenodesaredirectlyconnectedLAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAtotheedge-frontnodethroughanetworkcable.
WemakeuseoftwotypesofRaspberryPi(RPi)nodesasclients:onetypeisRPi2whichiswiredtotherouterwhiletheothertypeisRPi3whichisconnectedtorouterusingbuilt-in2.
4GHzWiFi.
6.
2.
2Datasets.
Wehaveemployedthreedatasetsforevaluation.
OnedatasetistheCaltechVisionGroup2001testingdatabase,inwhichthecarrearimageresolution(126imageswithresolution896x592)isadequateforlicenseplaterecognition[25].
Anotherdatasetisaself-collected4KvideocontainingrearlicenseplatestakenonanAndroidsmartphoneandisconvertedintovideosofdif-ferentresolutions(640x480,960x720,1280x960,and1600x1200).
eotherdatasetusedininter-edgecollaborationevaluationcontains22carimages,withthevariousresolutionrangingfrom405x540pixelsto2514x1210pixels(lesize316KBto2.
85MB).
etaskrequestsusethecarimagesasinputinaround-robinway,onecarimageforeachtaskrequest.
6.
3TaskProlerBesidetheroundtriptimeandbandwidthbenchmarkwehavepresentedinFig.
2andFig.
3tocharacterizetheedgecomputingnetwork,wehavedoneprolingoftheOpenALPRapplicationonvariousclient,edgeandcloudnodes.
Figure6:OpenALPRproleresultofclienttype1(RPi2quad-core0.
9GHz)Inthisexperiment,weusebothdataset1(workload1)anddataset2(workload2)atvariousresolutions.
eexecutiontimeforeachtasksareshowninFig.
6,Fig.
7,Fig.
8,andFig.
9.
eresultsindicatethatbyutilizinganedgenode,wecangetacomparableamountofcomputationpowerclosetoclientsforcomputation-intensivetasks.
Anotherobservationsisthat,duetotheunevenoptimizationonheterogeneousCPUarchitectures,sometasksarebeertokeeplocalwhilesomeothersshouldbeooadedtoedgecomputingnodes.
isobservationjustiestheneedofcomputationooadingbetweenclientsandedgenodes.
6.
4OloadingTaskSelectionTounderstandhowmuchtheexecutiontimecanbereducedbyspliingtasksbetweentheclientandtheedge,orbetweentheclientandthecloud,wedesignanexperimentwithworkloadsgeneratedfromdataset2ontwosetupsofscenarios:1)oneedgeFigure7:OpenALPRproleresultofclienttype2(RPi3quad-core1.
2GHz)Figure8:OpenALPRproleresultofatypeofedgenode(i7quad-core2.
30GHz)Figure9:OpenALPRproleofatypeofcloudnode(AWSEC2t2.
largeXeondual-core2.
40GHz)nodeprovidesservicetothreewiredclientnodesthathavethebestnetworklatencyandbandwidth;2)oneedgenodeprovidesservicetothreewireless2.
4GHzclientnodesthathavelatencywithhighvarianceandrelativelylowbandwidth.
eresultofSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAS.
Yietal.
Figure10:ecomparisonoftaskselectionimpactsonedgeoloadingandcloudoloadingforwiredclients(RPi2).
Figure11:ecomparisonoftaskselectionimpactsonedgeoloadingandcloudoloadingfor2.
4GHzwirelessclients(RPi3).
therstcaseisverystraightforward:theclientssimplyuploadalltheinputdataandrunallthetasksontheedgenodeinedgeooadingorcloudnodeincloudooading,asshowninFig.
10.
isismainlybecauseusingEthernetcablecanstablyprovidelowestlatencyandhighestbandwidth,whichmakesooadingtoedgeveryrewarding.
Wedidn'tevaluate5GHzwirelessclientsincethisinterfaceisnotsupportedonourclienthardwarewhileweanticipatesimilarresultsasthewirecase.
Weplottheresultofa2.
4GHzwirelessclientnodewithooadingtoanedgenodeoraremotecloudnodeinthesecondcaseinFig.
11.
Overall,theresultsshowedthatbyooadingtaskstoanedgecomputingplatform,theapplicationwehadchosenexperiencedaspeedupupto4.
0xonwiredclient-edgecongurationcomparedtolocalexecution,andupto1.
7xcomparedtoasimilarclient-cloudconguration.
Forclientswith2.
4GHzwirelessinterface,thespeedupisupto1.
3xonclient-edgecongurationcomparedtolocalexecution,andisupto1.
2xcomparedtosimilarclient-cloudconguration.
Figure12:ecomparisonresultofthreetaskprioritizingschemes.
6.
5Edge-frontTaskeuePrioritizingToevaluatetheperformanceofthetaskqueueprioritizing,wecollectthestatisticalresultsfromourprolerserviceandmoni-toringserviceonvariousworkloadforsimulation.
Wechoosethesimulationmethodbecausewecanfreelysetupthenumbersandtypesofclientandedgenodestoovercomethelimitationofourcurrenttestbedtoevaluatemorecomplexdeployments.
Weaddtwosimpleschemesasbaselines:1)shortestIOrst(SIOF):sortingallthetasksagainstthetimecostofthenetworktransmission;2)longestCPUlast(LCPUL):sortingallthetasksagainstthetimecostoftheprocessingontheedgenode.
Inthesimulation,basedonthecombinationofclientdevicetypes,workloadsandooadingdeci-sions,wehaveintotalseventypesofjobstorunontheedgenode.
WeincreasethetotalnumberofjobsandevenlydistributedthemamongtheseventypesandreportthemakespantimeinFig.
12.
eresultshowsthatLCPUListheworstamongthosethreeschemesandourschemeoutperformstheshortestjobrstscheme.
6.
6Inter-EdgeCollaborationWealsoevaluatethethreetaskplacementschemes(i.
e.
,STTF,SQLFandSSLF)discussedinSection5,throughacontrolledexperimentonourtestbed.
Forevaluationpurpose,wecongurethenetworkintheedgecomputingsystemasfollows.
erstedgenode,denotedas"edgenode#1",has10msRTTand40Mbpsbandwidthtotheedge-frontnode.
esecondedgenode,"edgenode#2",has20msRTTand20Mbpsbandwidthtotheedge-frontnode.
ethirdedgenode,"edgenode#3",has100msRTTand2Mbpsbandwidthtotheedge-frontnode.
us,weemulatethesituationwherethreeedgenodesareindierentdistancestotheedge-frontnode,fromneartofar.
Weusethethirddatasettosynthesizeaworkloadasfollows.
Intherst4minutes,theedge-frontnodereceives5taskrequestspersecond,edgenode#1receives4taskrequestspersecond,edgenode#2receives3taskrequestspersecond,andedgenode#3receives2taskrequestspersecond,respectively.
Notaskcomestoanyoftheedgenodesaertherst4minutes.
FortheSSLFtaskplacementscheme,weimplementasimplelinearregressiontopredicttheschedulinglatencyofthetaskbeingtransmied,sincetheworkloadwehaveinjectedisuniformdistributed.
LAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAFigure13:Performancewithnotaskplacementscheme.
Figure14:PerformanceofSTTF.
Figure15:PerformanceofSQLF.
Figure16:PerformanceofSSLF.
Fig.
13illustratesthethroughputoneachedgenode,whennotaskplacementschemeisenabledontheedge-frontnode.
eedge-frontnodehastheheaviestworkloadandittakesabout12.
36minutestonishallthetasks.
Weconsiderthisresultasourbase-line.
Fig.
14isthethroughputresultofSTTFscheme.
Inthiscase,theedge-frontnodeonlytransmitstaskstoedgenode#1,becauseedgenode#1hasthehighestbandwidthandtheshortestRTTtotheedge-frontnode.
Fig.
17revealsthattheedge-frontnodetransmits120taskstoedgenode#1andnotasktootheredgenodes.
Asedgenode#1hasheavierworkloadthanedgenode#2andedgenode#3,theSTTFschemehaslimitedimprovementonthesystemperformance:theedge-frontnodetakesabout11.
29minutestonishallthetasks.
Fig.
15illustratesthethroughputresultofSQLFscheme.
isschemeworksbeerthantheSTTFscheme,becausetheedge-frontnodetransmitsmoretaskstoless-saturatededgenodes,ecientlyreducingtheworkloadontheedge-frontnode.
However,theedge-frontnodeintendstotransmitmanytaskstoedgenode#3atthebeginning,whichhasthelowestbandwidthandthelongestRTTtotheedge-frontnode.
Assuch,thetaskplacementmayincurmoredelaythenexpected.
FromFig.
17,theedge-frontnodetransmits0tasktoedgenode#1,132taskstoedgenode#2,and152taskstoedgenode#3.
eedge-frontnodetakesabout9.
6minutestonishallthetasks.
Fig.
16demonstratesthethroughputresultofSSLFscheme.
isschemeconsidersboththetransmissiontimeofthetaskbeingplacedandthewaitingtimeinthequeueonthetargetedgenode,andthereforeachievesthebestperformanceofthethree.
Asmen-tioned,edgenode#1hasthelowesttransmissionoverheadbuttheheaviestworkloadamongthethreeedgenodes,whileedgenode#3hasthelightestworkloadbutthehighesttransmissionoverhead.
Incontrast,edgenode#2hasmodesttransmissionoverheadandmodestworkload.
eSSLFschemetakesallthesesituationsintoconsideration,andplacesthemostnumberoftasksonedgenode#2.
AsshowninFig.
17,theedge-frontnodetransmits4taskstoedgenode#1,152taskstoedgenode#2,and148taskstoedgenode#3whenworkingwiththeSSLFscheme.
eedge-frontnodetakesabout9.
36minutestonishallthetasks,whichisthebestresultamongthethreeschemes.
Weinferthatthethirdschemewillfurtherimprovethetaskcompletiontimeifmoretoughnetworkconditionsandworkloadsareconsidered.
7RELATEDWORKeemergenceofedgecomputinghasdrawnaentionsduetoitscapabilitiestoreshapethelandsurfaceofIoTs,mobilecomputing,SEC'17,October12–14,2017,SanJose/SiliconValley,CA,USAS.
Yietal.
Figure17:Numbersoftasksplacedbytheedge-frontnode.
andcloudcomputing[6,14,32,33,36–38].
Satyanarayanan[29]hasbriefedtheoriginofedgecomputing,alsoknownasfogcomput-ing[4],cloudlet[28],mobileedgecomputing[24]andsoon.
Herewewillreviewseveralrelevantresearcheldstowardsvideoedgeanalytics,includingdistributeddataprocessingandcomputationooadinginvariouscomputingparadigms.
7.
1DistributedDataProcessingDistributeddataprocessinghascloserelationshiptotheedgean-alyticsinthesensethatthosedataprocessingplatforms[9,39]andunderlyingtechniques[16,23,27]canbeeasilydeployedonaclusterofedgenodes.
Inthispaper,wepayspeciallyaentionstodistributedimage/videodataprocessingsystems.
VideoStorm[40]madeinsightfulobservationonvision-relatedalgorithmsandpro-posedresource-qualitytrade-owithmulti-dimensionalcongu-rations(e.
g.
videoresolution,framerate,samplingrate,slidingwindowsize,etc.
).
eresource-qualityprolesaregeneratedof-ineandaonlineschedulerisbuilttoallocateresourcestoqueriestooptimizetheutilityofqualityandlatency.
eirworkiscomple-mentarytoours,inthatwedonotconsiderthetrade-obetweenqualityandlatencygoalsviaadaptivecongurations.
Vigil[42]isawirelessvideosurveillancesystemthatleveragededgecomput-ingnodeswithemphasisonthecontent-awareframeselectionsinascenariowheremultiplewebcamerasareatthesamelocationtooptimizethebandwidthutilization,whichisorthogonaltotheproblemswehaveaddressedhere.
Firework[41]isacomputingparadigmforbigdataprocessingincollaborativeedgeenvironment,whichiscomplementarytoourworkintermsofshareddataviewandprogramminginterface.
Whilethereshouldbemoreon-goingeortsforinvestigatingtheadaptation,improvement,andoptimizationofexistingdistributeddataprocessingtechniquesonedgecomputingplatform,wefocusmoreonthetask/application-levelqueuemanagementandsched-uling,andleavealltheunderlyingresourcenegotiating,processschedulingtothecontainerclusterengine.
7.
2ComputationOloadingComputationooading(a.
k.
a.
Cyberforaging[28])hasbeenpro-posedtoimproveresourceutilization,responsetime,andenergyconsumptioninvariouscomputingenvironments[7,13,21,31].
Work[17]hasquantiedtheimpactofedgecomputingonmobileapplicationsandfoundthatedgecomputingcanimproveresponsetimeandenergyconsumptionsignicantlyformobiledevicesthroughooadingviabothWiFiandLTEnetworks.
Mocha[34]hasinvestigatedhowatwo-stagefacerecognitiontaskfrommobiledevicecanbeacceleratedbycloudletandcloud,Intheirdesign,clientssimplycaptureimageandsendstocloudlet.
eoptimaltaskpartitioncanbeeasilyachievedasithasonlytwostages.
InLAVEA,ourapplicationismorecomplicatedinmultiplestagesandweleverageclient-edgeooadingandothertechniquestoimprovetheresourceutilizationandoptimizetheresponsetime.
8DISCUSSIONSANDLIMITATIONSInthissection,wewilldiscussalternativedesignoptions,pointoutcurrentlimitations,andidentifyfutureworkthatcanimprovethesystem.
Measurement-basedOloading.
Inthispaper,weutilizeameasurement-basedooading(staticooading),i.
e,theooadingdecisionsarebasedontheoutcomeofperiodicmeasurements.
Weconsiderthisasoneofthelimitationsofourimplementations,asstatedin[15]andthereareseveraldynamiccomputationooadingschemeshavebeenproposed[12].
Weareplanningtoimprovethemeasurement-basedooadinginthefuturework.
VideoStreaming.
Ourcurrentdataprocessingisimage-based,whichisoneofthelimitationsofourimplementation.
einputiseitherintheformatofimageorinvideostreamwhichisreadintoframesandsentout.
Webelievethatutilizingexistingvideostreamingtechniquesinbetweenoursystemcomponentsfordatasharingwillfurtherimprovesthesystemperformanceandopensmorepotentialopportunitiesforoptimization.
DiscoveringEdgeNodes.
erearedierentwaysfortheedge-frontnodetodiscovertheavailableedgenodesnearby.
Forexample,everyedgenodeintendingtoserveasacollaboratormayopenadesignatedport,sothattheedge-frontnodecanperiodicallyscanthenetworkanddiscovertheavailableedgenodes.
isiscalledthe"pull-based"method.
Incontrast,thereisalsoa"push-based"method,inwhichtheedge-frontnodeopensadesignatedport,andeveryedgenodeintendingtoserveasacollaboratorwillregistertotheedge-frontnode.
Whenthenetworkisinalargescale,thepull-basedmethodusuallyperformspoorlybecausetheedge-frontnodemaynotbeabletodiscoveranavailableedgenodeinashorttime.
Forthisreason,theedgenodediscoveryshouldbeimplementedinapush-basedmethod,whichguaranteesgoodperformanceregardlessofthenetworkscale.
9CONCLUSIONInthispaper,wehaveinvestigatedhowtoprovidevideoanalyticservicestolatency-sensitiveapplicationsinedgecomputingenvi-ronment.
Asaresult,wehavebuiltLAVEA,alow-latencyvideoedgeanalyticsystem,whichcollaboratesnearbyclient,edgeandremotecloudnodes,andtransfersvideofeedsintosemanticinfor-mationatplacesclosertotheusersinearlystages.
Wehaveutilizedanedge-frontdesignandformulatedanoptimizationproblemforooadingtaskselectionandprioritizedtaskqueuetominimizetheresponsetime.
Ourresultindicatesthatbyooadingtaskstotheclosestedgenode,theclient-edgecongurationhasa1.
3xto4xLAVEA:Latency-awareVideoAnalyticsonEdgeComputingPlatformSEC'17,October12–14,2017,SanJose/SiliconValley,CA,USA(1.
2xto1.
7x)speedupagainstrunninglocally(client-cloud)undervariousnetworkconditionsandworkloads.
Incaseofasaturatingworkloadonthefrontedgenode,wehaveproposedandcomparedvarioustaskplacementschemesthataretailedforinter-edgecollab-oration.
eproposedprediction-basedshortestschedulinglatencyrsttaskplacementschemeconsidersboththetransmissiontimeofthetasksandthewaitingtimeinthequeue,andoutputsbeeroverallperformancethantheotherschemes.
REFERENCES[1]AmazonWebService.
2017.
AWSLambda@Edge.
hp://docs.
aws.
amazon.
com/lambda/latest/dg/lambda-edge.
html.
(2017).
[2]Christos-NikolaosEAnagnostopoulos,IoannisEAnagnostopoulos,IoannisDPsoroulas,VassiliLoumos,andEleheriosKayafas.
2008.
Licenseplaterecog-nitionfromstillimagesandvideosequences:Asurvey.
IEEETransactionsonintelligenttransportationsystems9,3(2008),377–391.
[3]KRBaker.
1990.
Schedulinggroupsofjobsinthetwo-machineowshop.
Math-ematicalandComputerModelling13,3(1990),29–36.
[4]FlavioBonomi,RodolfoMilito,JiangZhu,andSateeshAddepalli.
2012.
Fogcomputinganditsroleintheinternetofthings.
InProceedingsofthersteditionoftheMCCworkshoponMobilecloudcomputing.
ACM,13–16.
[5]PeterBrucker,BerndJurisch,andBerndSievers.
1994.
Abranchandboundalgorithmforthejob-shopschedulingproblem.
Discreteappliedmathematics49,1(1994),107–127.
[6]YuCao,SongqingChen,PengHou,andDonaldBrown.
2015.
FAST:Afogcom-putingassisteddistributedanalyticssystemtomonitorfallforstrokemitigation.
InNetworking,ArchitectureandStorage(NAS),2015IEEEInternationalConferenceon.
IEEE,2–11.
[7]EduardoCuervo,ArunaBalasubramanian,Dae-kiCho,AlecWolman,StefanSaroiu,RanveerChandra,andParamvirBahl.
2010.
MAUI:MakingSmartphonesLastLongerwithCodeOoad.
InProceedingsofthe8thInternationalConferenceonMobileSystems,Applications,andServices(MobiSys'10).
ACM,NewYork,NY,USA,49–62.
DOI:hps://doi.
org/10.
1145/1814433.
1814441[8]EyaldeLara,CarolinaSGomes,SteveLangridge,SHosseinMortazavi,andMeysamRoodi.
2016.
HierarchicalServerlessComputingfortheMobileEdge.
InEdgeComputing(SEC),IEEE/ACMSymposiumon.
IEEE,109–110.
[9]JereyDeanandSanjayGhemawat.
2008.
MapReduce:simplieddataprocessingonlargeclusters.
Commun.
ACM51,1(2008),107–113.
[10]ShanDu,MahmoudIbrahim,MohamedShehata,andWaelBadawy.
2013.
Auto-maticlicenseplaterecognition(ALPR):Astate-of-the-artreview.
IEEETransac-tionsoncircuitsandsystemsforvideotechnology23,2(2013),311–325.
[11]SadjadFouladi,RiadS.
Wahby,BrennanShackle,KarthikeyanVasukiBalasubra-maniam,WilliamZeng,RahulBhalerao,AnirudhSivaraman,GeorgePorter,andKeithWinstein.
2017.
Encoding,FastandSlow:Low-LatencyVideoProcessingUsingousandsofTinyreads.
In14thUSENIXSymposiumonNetworkedSystemsDesignandImplementation(NSDI17).
USENIXAssociation,Boston,MA,363–376.
hps://www.
usenix.
org/conference/nsdi17/technical-sessions/presentation/fouladi[12]WeiGao,YongLi,HaoyangLu,TingWang,andCongLiu.
2014.
Onexploitingdynamicexecutionpaernsforworkloadooadinginmobilecloudapplications.
InNetworkProtocols(ICNP),2014IEEE22ndInternationalConferenceon.
IEEE,1–12.
[13]MarkSGordon,DavoudAnousheJamshidi,ScoAMahlke,ZhuoqingMor-leyMao,andXuChen.
2012.
COMET:CodeOoadbyMigratingExecutionTransparently.
.
InOSDI,Vol.
12.
93–106.
[14]ZijiangHao,EdNovak,ShanheYi,andnLi.
2017.
ChallengesandSowareArchitectureforFogComputing.
InternetComputing(2017).
[15]MohammedAHassan,KshitizBhaarai,QiWei,andSongqingChen.
2014.
POMAC:ProperlyOoadingMobileApplicationstoClouds.
In6thUSENIXWorkshoponHotTopicsinCloudComputing(HotCloud14).
[16]BenjaminHindman,AndyKonwinski,MateiZaharia,AliGhodsi,AnthonyDJoseph,RandyHKatz,ScoShenker,andIonStoica.
2011.
Mesos:APlatformforFine-GrainedResourceSharingintheDataCenter.
.
InNSDI,Vol.
11.
22–22.
[17]WenluHu,YingGao,KiryongHa,JunjueWang,BrandonAmos,ZhuoChen,PadmanabhanPillai,andMahadevSatyanarayanan.
2016.
antifyingtheImpactofEdgeComputingonMobileApplications.
InProceedingsofthe7thACMSIGOPSAsia-PacicWorkshoponSystems.
ACM,5.
[18]IBM.
2017.
ApacheOpenWhisk.
hp://openwhisk.
org/.
(April2017).
[19]SelmerMartinJohnson.
1954.
Optimaltwo-andthree-stageproductionscheduleswithsetuptimesincluded.
Navalresearchlogisticsquarterly1,1(1954),61–68.
[20]EricJonas,ShivaramVenkataraman,IonStoica,andBenjaminRecht.
2017.
OccupytheCloud:Distributedcomputingforthe99%.
arXivpreprintarXiv:1702.
04024(2017).
[21]RyanNewton,SivanToledo,LewisGirod,HariBalakrishnan,andSamuelMad-den.
2009.
Wishbone:Prole-basedPartitioningforSensornetApplications.
.
InNSDI,Vol.
9.
395–408.
[22]OpenALPR.
2017.
OpenALPR–AutomaticLicensePlateRecognition.
hp://www.
openalpr.
com/.
(April2017).
[23]KayOusterhout,PatrickWendell,MateiZaharia,andIonStoica.
2013.
Sparrow:distributed,lowlatencyscheduling.
InProceedingsoftheTwenty-FourthACMSymposiumonOperatingSystemsPrinciples.
ACM,69–84.
[24]MPatel,BNaughton,CChan,NSprecher,SAbeta,ANeal,andothers.
2014.
Mobile-edgecomputingintroductorytechnicalwhitepaper.
WhitePaper,Mobile-edgeComputing(MEC)industryinitiative(2014).
[25]BradPhilipandPaulUpdike.
2001.
CaltechVisionGroup2001testingdatabase.
hp://www.
vision.
caltech.
edu/html-les/archive.
html.
(2001).
[26]KariPulli,AnatolyBaksheev,KirillKornyakov,andVictorEruhimov.
2012.
Real-timecomputervisionwithOpenCV.
Commun.
ACM55,6(2012),61–69.
[27]JeRasley,KonstantinosKaranasos,SrikanthKandula,RodrigoFonseca,MilanVojnovic,andSriramRao.
2016.
Ecientqueuemanagementforclustersched-uling.
InProceedingsoftheEleventhEuropeanConferenceonComputerSystems.
ACM,36.
[28]MahadevSatyanarayanan.
2001.
Pervasivecomputing:Visionandchallenges.
IEEEPersonalcommunications8,4(2001),10–17.
[29]MahadevSatyanarayanan.
2017.
eEmergenceofEdgeComputing.
Computer50,1(2017),30–39.
[30]MahadevSatyanarayanan,PieterSimoens,YuXiao,PadmanabhanPillai,ZhuoChen,KiryongHa,WenluHu,andBrandonAmos.
2015.
Edgeanalyticsintheinternetofthings.
IEEEPervasiveComputing14,2(2015),24–31.
[31]CongShi,KarimHabak,PraneshPandurangan,MostafaAmmar,MayurNaik,andEllenZegura.
2014.
Cosmos:computationooadingasaserviceformobiledevices.
InProceedingsofthe15thACMinternationalsymposiumonMobileadhocnetworkingandcomputing.
ACM,287–296.
[32]W.
Shi,J.
Cao,Q.
Zhang,Y.
Li,andL.
Xu.
2016.
EdgeComputing:VisionandChallenges.
IEEEInternetofingsJournal3,5(Oct2016),637–646.
DOI:hps://doi.
org/10.
1109/JIOT.
2016.
2579198[33]WeisongShiandSchahramDustdar.
2016.
ePromiseofEdgeComputing.
Computer49,5(2016),78–81.
[34]TolgaSoyata,RajaniMuraleedharan,ColinFunai,MinseokKwon,andWendiHeinzelman.
2012.
Cloud-Vision:Real-timefacerecognitionusingamobile-cloudlet-cloudaccelerationarchitecture.
InComputersandCommunications(ISCC),2012IEEESymposiumon.
IEEE,000059–000066.
[35]XiaoliWang,AakankshaChowdhery,andMungChiang.
2016.
SkyEyes:adaptivevideostreamingfromUAVs.
InProceedingsofthe3rdWorkshoponHotTopicsinWireless.
ACM,2–6.
[36]ShanheYi,ZijiangHao,ZhengruiQin,andnLi.
2015.
FogComputing:Plat-formandApplications.
InHotTopicsinWebSystemsandTechnologies(HotWeb),2015irdIEEEWorkshopon.
IEEE,73–78.
[37]ShanheYi,ChengLi,andnLi.
2015.
ASurveyofFogComputing:Concepts,ApplicationsandIssues.
InProceedingsofthe2015WorkshoponMobileBigData,Mobidata'15.
ACM,37–42.
[38]ShanheYi,ZhengruiQin,andnLi.
2015.
Securityandprivacyissuesoffogcomputing:Asurvey.
InWirelessAlgorithms,Systems,andApplications.
Springer,685–695.
[39]MateiZaharia,MosharafChowdhury,MichaelJFranklin,ScoShenker,andIonStoica.
2010.
Spark:clustercomputingwithworkingsets.
HotCloud10(2010),10–10.
[40]HaoyuZhang,GaneshAnanthanarayanan,PeterBodik,MahaiPhilipose,ParamvirBahl,andMichaelJ.
Freedman.
2017.
LiveVideoAnalyticsatScalewithApproximationandDelay-Tolerance.
In14thUSENIXSymposiumonNetworkedSystemsDesignandImplementation(NSDI17).
USENIXAssociation,Boston,MA,377–392.
hps://www.
usenix.
org/conference/nsdi17/technical-sessions/presentation/zhang[41]Q.
Zhang,X.
Zhang,Q.
Zhang,W.
Shi,andH.
Zhong.
2016.
Firework:BigDataSharingandProcessinginCollaborativeEdgeEnvironment.
In2016FourthIEEEWorkshoponHotTopicsinWebSystemsandTechnologies(HotWeb).
20–25.
DOI:hps://doi.
org/10.
1109/HotWeb.
2016.
12[42]TanZhang,AakankshaChowdhery,ParamvirVictorBahl,KyleJamieson,andSumanBanerjee.
2015.
edesignandimplementationofawirelessvideosurveillancesystem.
InProceedingsofthe21stAnnualInternationalConferenceonMobileComputingandNetworking.
ACM,426–438.