publiclyamazonec2

VirtualNetworkEmbeddingThroughTopology-AwareNodeRankingXiangCheng,SenSu,ZhongbaoZhang,HanchiWang,FangchunYangBeijingUniversityofPostsandTelecommunications{chengxiang,susen,zhongbaozb,luigiking,fcyang}@bupt.
edu.
cnYanLuo,JieWangUniversityofMassachusettsLowellyanluo@uml.
edu,wang@cs.
uml.
eduABSTRACTVirtualizingandsharingnetworkedresourceshavebecomeagrowingtrendthatreshapesthecomputingandnetworkingarchitectures.
Embeddingmultiplevirtualnetworks(VNs)onasharedsubstrateisachallengingproblemoncloudcom-putingplatformsandlarge-scalesliceablenetworktestbeds.
InthispaperweapplytheMarkovRandomWalk(RW)modeltorankanetworknodebasedonitsresourceandtopologicalattributes.
Thisnoveltopology-awarenoderank-ingmeasurereectstherelativeimportanceofthenode.
Us-ingnoderankingwedevisetwoVNembeddingalgorithms.
Therstalgorithmmapsvirtualnodestosubstratenodesaccordingtotheirranks,thenembedsthevirtuallinksbe-tweenthemappednodesbyndingshortestpathswithun-splittablepathsandsolvingthemulti-commodityowprob-lemwithsplittablepaths.
Thesecondalgorithmisaback-trackingVNembeddingalgorithmbasedonbreadth-rstsearch,whichembedsthevirtualnodesandlinksduringthesamestageusingnoderanks.
Extensivesimulationexperi-mentsshowthatthetopology-awarenoderankisabetterresourcemeasureandtheproposedRW-basedalgorithmsin-creasethelong-termaveragerevenueandacceptanceratiocomparedtotheexistingembeddingalgorithms.
CategoriesandSubjectDescriptorsC.
2.
5[Computer-CommunicationNetworks]:LocalandWide-AreaNetworks;G.
1.
6[NumericalAnalysis]:Opti-mizationGeneralTermsAlgorithms;Design;PerformanceKeywordsNetworkVirtualization;CloudComputing;VirtualNetworkEmbedding;Topology-aware;RandomWalk;MarkovChain1.
INTRODUCTIONSharingvirtualizedresourcesenablesnewcomputingandnetworkingparadigmssuchascloudbasedcomputingplat-forms[1]andsliceablenetworktestbeds[15].
UsersofacloudplatformoranetworkinfrastructurerequesttheirshareofresourcesincludingCPUcapacities,storagespace,networkbandwidth,etc.
,whiletheinfrastructureprovidersCorrespondingauthorofthispaperisProf.
SenSumaketheirbesteorttoservetherequests,whicharealsoknownasvirtualnetworks(VNs).
Theallocationofre-sourcestoVNsinsuchavirtualizationenvironmentiscriti-caltobothusers'computationneedsandtheresourceproviders'monetarygain.
Inthemulti-tenantnetworkvirtualizationenvironments,infrastructureproviders(InPs)(e.
g.
,cloudproviders)andserviceproviders(SPs)(e.
g.
,cloudusers/tenants)playtwodecoupledroles,namely,InPsmanagethephysicalinfras-tructurewhileSPscreateVNsandoerend-to-endservices[27,14,8].
MappingVNrequestsoftheSPsontothesub-stratenetworkoftheInPs,alsoknownasVNembedding,isNP-hard[28,5].
Thus,devisingheuristicshasbecomethemainlineofresearchinVNembedding[13,29,22,28].
TheearlyalgorithmsmeasuretheresourceofanodebyitsCPUcapacity,orbandwidth,orboth,withoutconsideringthetopologicalstructureoftheVNsandtheunderlyingsub-stratenetwork.
Yetthetopologicalattributesofnodeshavesignicantimpactonthesuccessandeciencyofmappingoutcomes.
Itwouldmakesensetomeasureanode'sre-sourcesanditstopologicalattributesatthesametime.
InspiredbyPageRankusedbyGoogle'ssearchengine,whichmeasuresthepopularityofwebpagesbasedonMarkovrandomwalks,weusethesametheorytomeasuretopology-awareresourcerankingofanode,calledNodeRank,whichreectstheresourceandqualityofconnectionsofanode.
PageRankconsidersalinkfrompageAtopageBasavote,andapageisconsideredimportantifanumberofimportantpagesvotetoit.
Insuchaway,thetopologyoftheworldwidewebinuencesthePageRankofawebpage.
InVNem-bedding,ifanodelinksforwardtoanumberofnodeswithrelativelyhighimportance,thisnodewouldalsobeconsid-eredimportant,wheretheimportancereferstotherelativeresourcequalityofanode.
WewilltakeintoaccountnotonlytheavailabilityorrequirementsoftheCPUandlinkre-sourcesofthenode,butalsoitstopologicalcharacteristics,i.
e.
,thequalityofitsneighbors.
TreatingtheconnectivitybetweentwonodesasaMarkovchaintransitionwithcertainprobability,wecancalculatetherelativeresourcequalityofanodewithaMarkovchainmodelbasedonthetopologyofthenetwork.
WedevisetwonewVNembeddingalgorithmscalledRW-MaxMatchandRW-BFSbasedonNodeRanks.
TheyrstcomputethenoderankforeachnodeintheVNrequestandforeachnodeintheresidualsubstratenetwork.
RW-MaxMatchisatwo-stageVNembeddingalgorithm.
Intherststageitmapsavirtualnodewiththehighestranktoasubstratenodewiththehighestrank,avirtualnodewiththesecondhighestranktoasubstratenodewiththesec-ondhighestrank,andcontinuesinthismannerfortherestofthevirtualnodes.
Inthesecondstageitembedsvir-tuallinksusingtheshortestpathalgorithmifpathsplitting[28]isnotsupportedbythesubstratenetwork,orusingthemulti-commodityowalgorithmifthesubstratesupportspathsplitting.
Similartotheexistingtwo-stageVNEal-gorithms,RW-MaxMatchmayleadtohighersubstratenet-workresourceconsumptionandrestricttheabilityofthesubstratetoacceptadditionalfuturerequests.
RW-BFScanhelpsolvethisproblem.
ItisabacktrackingVNembeddingalgorithmbasedonbreadth-rstsearchthatmapsvirtualnodesandvirtuallinksduringthesamestage,aimingtoincreasetheresourceutilizationofthesubstrateresource.
Extensivesimulationexperimentsshowthatthetopology-awarenoderankisabetternoderesourcemeasureandtheproposedRW-basedalgorithmsincreasethelong-termav-eragerevenueandacceptanceratiocomparedtoexistingembeddingalgorithms.
Thispaperpresentsthefollowingmajorcontributions:WeformulateaMarkovrandomwalkmodeltocom-putetopology-awareresourcerankingofnodesinanetwork,whichservesasthebasisofembeddingvir-tualnetworksonsubstratenetworks.
Tothebestofourknowledge,thisworkisthersttoapplyrandomwalksinsolvingVNEproblems.
WedevisetwoVNEalgorithmsbasedontopology-awarenoderanks.
Bothtwo-stageandone-stagemap-pingstrategiesareinvestigated.
Weconductathoroughcomparisonbetweenouralgo-rithmsandawiderangeofexistingalgorithmsthroughextensivesimulations.
WedesignaVNEsimulatorandmakeitpubliclyavailabletotheresearchcommunity.
Therestofthepaperisorganizedasfollows.
InSection2,wediscusstherelatedwork.
Section3presentsthenet-workmodelandformalizestheVNembeddingproblem.
InSection4wepresentthemethodofcomputingthetopology-awareresourceranksofnodesusingtherandomwalkmodel.
Section5describesRW-MaxMatchandRW-BFS.
TheVNembeddingalgorithmsareevaluatedinSection6.
Section7concludesthepaper.
2.
RELATEDWORKTheVNembeddingproblemissimilartothevirtualpri-vatenetwork(VPN)provisioningproblem[18].
Thema-jordierencebetweenthemisonresourceconstraints.
InatypicalVPNrequest,theonlyresourceconstraintsareband-widthrequirementsfromsourcestodestinationsspeciedbyatracmatrix.
Therearetypicallynoresourceconstraintsonthenodes(e.
g.
,CPU)andtheirlocations.
Anothersim-ilarproblemisthenetworktestbedmappingproblem.
TheAssignalgorithm[24]usedintheEmulabtestbedconsidersconstraintsonbothnodesandlinks,wherethenodecon-straintisprovidedastheexclusiveuseofnodes,i.
e.
,dier-entvirtualnetworkscannotsharethesamesubstratenode.
VNembedding,however,allowssubstratenodesandlinkstobesharedbymultipleVNs.
EarlystudiesonVNembeddingeitherassumethattheVNrequestsareknowninadvance(anoineversion)[29,22];ordealwithatmostonetypeofconstraints(nodeorlink)[13,29,22];orperformnoadmissioncontrolwhentheresourceofthesubstratenetworkisinsucient[13,29,22];orfocusonlyonthebackbone-startopology[22].
Withoutreducingtheproblemspace,Yuetal.
[28]intro-ducethemechanismsofsubstratesupportingpathsplittingandmigration.
Chowdhuryetal.
[9],whileconsideringthesameonlineVNembeddingproblemspaceasin[28],alsoconsiderlocationrequirementsofvirtualnodesandusemixedintegerprogramming(MIP)tosolvetheVNembed-dingproblem.
Lischkaetal.
[21]modelthetopologyofthesubstrateandthevirtualnetworkasadirectedgraph,andproposeaVNembeddingalgorithmbasedonsubgraphisomorphismwhichmapsnodesandlinksduringthesamestage.
TheiralgorithmcanbeseenasaextendedversionoftheclassicVFgraphmatchingalgorithms[10],wherelink-on-linkmappinghasbeenrelaxed.
Houidietal.
[20]presentadistributedVNembeddingalgorithmthatachievesembeddingthroughcommunicat-ingandexchangingmessagesbetweenagent-basedsubstratenodes.
Althoughcentralizedalgorithmscouldsuerfromasinglepointoffailure,theperformanceandscalabilityoftheproposeddistributedalgorithmcompareunfavorablywiththoseofthecentralizedalgorithms.
Tomaximizetheaggregateperformanceacrossvirtualnetworks,Heetal.
[19]proposeanarchitecturalframeworkcalledDaVincitodynamicallyadaptvirtualnetworksforacustomizednetworksubstrate,whereeachsubstratelinkperiodicallyreassignsbandwidthamongitsvirtuallinks.
Whileonasmallertimescale,adistributedprotocolisrunineachVNtomaximizetheVN'sownperformanceobjec-tiveindependently.
DaVinci,however,doesnothaveanodeembeddingstage.
SincethenetworkconditionchangeovertimeduetothearrivalanddepartureofVNs,resourcesinthesubstratenet-workmaybecomefragmented.
Buttetal.
[7]presentatopology-awaremeasureusingscalingfactorsforthesub-stratenetwork,whichidentiesthebottlenecknodesandlinksinthesubstratenetwork.
Theythenproposeasetofalgorithmsforre-optimizingandre-embeddinginitially-rejectedVNrequests.
Recently,Guoetal.
proposedadatacenternetworkvir-tualizationarchitecturecalledSecondNet[17].
InSecond-Net,theunitofresourceallocationformultipletenantsinthecloudisreferredasvirtualdatacenter(VDC)whichconsistsofvirtualmachinesandvirtuallinks.
TheVDCre-sourceallocationproblemiscloserelatedtotheVNembed-dingproblemandthemaindierenceistheproblemscale.
TheVDCresourceallocationalgorithmsproposedin[17]primarilyfocusonhowtoquicklyallocatetheresourcestotheVDCswhenaVDChasthousandsofvirtualmachinesandthecloudinfrastructurehastenstohundredsofthou-sandsserversandswitches,andhowtosatisfytheelasticityrequirementofVDCs.
Webelievethatthetopology-awarenoderankingmethodisgeneralenoughtobeappliedintheircontexttoincreasethepossibilityofsatisfyingtheresourcerequirementsofVDCs.
Pageetal.
[23]userandomwalkstoranktherelativeimportanceofwebpages,wheretherankofapagedependsonthetopologicalpropertiesoftheweightedlinksbetweenthepages,regardlessoftheircontent.
Amoregeneralframe-workforthisschemewasproposedin[11].
Anotherexampleabc2020151215VNRequest2VNRequest1ADECFB302030104050bacd2025404030301520(c)(d)ADECFB301010103030cba2025252520201520SubstrateNetworkabdc1010202015101015(a)(b)SubstrateNetworkFigure1:ExamplesofVNembeddingofusingrandomwalksistocomputeasetoftopologicalsig-naturesforeachnodeinagraph,anditisalsoshowntobeeectiveforexact(andapproximate)graphmatching(see[16]).
Inatypicalgraphmatchingproblem,thereareeithernoweightsonthenodesorlinks,orthereareonlyvisualfea-tures(e.
g.
,RGBcolorspace)containedinthenodeswith-outlinks.
UnlikePageRankandgraphmatching,however,intheVNembeddingproblemthereareweightsonbothnodesandlinks,andtheweightsaretypicallynon-uniform.
Ourworkdiersfromtheexistingstudiesinthreeways.
First,weaddresstheonlineVNembeddingproblemwithadmissioncontrol,anddonotneedtoreduceproblemspaceasin[29,22,13].
Second,weconsiderboththeresourceamountandtopologypropertiesofanodeinauniedwaytoranktherelativeimportanceofanode,whichwillbelever-agedinthemappingprocedure.
Dierentfromexistingworkthatonlytakesintoconsiderationtheresource(e.
g.
,CPU,bandwidth,orboth)ofanodewhileneglectingitstopologypropertyincomputingtheresourceavailability,ourworkmendsthisgap.
Third,ourtopology-awarenoderankingmeasurefocusesonleveragingsucharanktobenetthecurrentVNembeddingprocessratherthanidentifyingthebottlenecksofthesubstratenodesandlinksfortheVNem-beddingreoptimizationprocessproposedin[7].
InSection4wewillprovidedetailshowweapplytherandomwalkmodeltocomputethetopology-awarenoderesourceranks.
3.
NETWORKMODELANDPROBLEMDE-SCRIPTIONSubstrateNetworks.
Asubstratenetworkcanberepre-sentedbyaweightedundirectedgraphGs=(Ns,Ls,Ans,Als),whereNsisthesetofsubstratenodesandLsthesetofsub-stratelinks.
ThenotationsAnsandAlsdenotetheattributesofthesubstratenodesandlinks,respectively.
Theattributesofthenodeincludeprocessingcapacity,storage,andloca-tion.
Thetypicalattributeofthelinkisitsbandwidth.
InthispaperweconsidertheavailableCPUcapacityforthenodeattributeandtheavailablebandwidthforthelinkat-tributeasinmostofthepreviousresearch.
DenotebyPsthesetofallloop-freepathsofthesubstratenetwork.
Fig.
1(b)presentsasubstratenetwork,wherethenumbersinrectanglesaretheavailableCPUresourcesatthenodesandthenumbersoverthelinksrepresentavailablebandwidths.
VirtualNetworkRequest.
Similartothesubstratenet-work,weuseanundirectedgraphGv=(Nv,Lv,Cnv,Clv)todenoteavirtualnetwork,whereNvisthesetofvirtualnodesandLvthesetofvirtuallinks.
Virtualnodesandlinksareassociatedwiththeircapacityconstraints,denotedbyCnvandClv,respectively.
WealsodenoteaVNrequestbyVNR(i)(Gv,ta,td),wheretaisthearrivaltimeoftheVNRandtdthedurationoftheVNstayinginthesub-stratenetwork.
Whenthei-thVNRarrives,thesubstratenetworkshouldallocateresourcestotheVNtomeettherequirementsofthevirtualnodesandlinks.
Iftherearenosucientsubstrateresourcesavailable,theVNRshouldberejectedorpostponed.
TheallocatedsubstrateresourcesarereleasedwhentheVNdeparts.
TheremaybedierentrolesofallnodeinusingVNs,suchasdirectoryorleserveretc.
Forsimplicity,likemostofthepreviouswork[28,9],weignorethesedependencies.
Fig.
1(a)andFig.
1(c)presenttwoVNrequestswithnodeandlinkrequirements.
VNEmbeddingProblemDescription.
TheVNembed-dingproblemisdenedbyamappingM:Gv(Nv,Lv)→Gs(Ns,Ps)fromGvtoasubsetofGs,whereNsNsandPsPs.
Themappingcanbedecomposedintotwomappingsteps:(i)nodemappingplacesthevirtualnodestodierentsubstratenodesthatsatisfythenoderesourceconstraints;and(ii)linkmappingassignsthevirtuallinkstoloop-freepathsonthesubstratethatsatisfythelinkre-sourcerequirements.
Fig.
1(a)andFig.
1(b)showaVNembeddingsolutionforVNR1.
Fig.
1(c)andFig.
1(d)showanotherVNembeddingsolutionforVNR2,whereresidualresourcesarealsoshown.
NotethatthevirtualnodesofdierentVNRscanbemappedontothesamesubstratenode.
Objectives.
ThemainobjectiveofVNembeddingistomaptheVNstothesubstratenetworktomakeecientuseofthesubstratenetworkresources,whentheVNrequestsarriveanddepartovertime.
Similartothepreviousworkin[29,28,9],therevenueofacceptingaVNRattimetcanbeformulatedbyR(Gv,t)=Xdv∈NvCPU(dv)+Xlv∈LvBW(Lv),(1)whereCPU(dv)andBW(Lv)aretheCPUandtheband-widthrequirementsforvirtualnodedvandlinklv,respec-tively.
ThecostofacceptingaVNRattimetisdenedasthesumofthetotalsubstrateresourcesallocatedtothatVN:C(Gv,t)=Xdv∈NvCPU(dv)+Xlv∈LvXls∈LsBW(flvls,lv),(2)whereflvls∈{0,1}andflvls=1ifsubstratelinklsallocatedbandwidthresourcetovirtuallinklv,otherwiseflvls=0.
BW(flvls,lv)isthebandwidthallocatedtolvfromls.
FromtheInPs'pointofview,anecientandeectiveon-lineVNembeddingalgorithmwouldmaximizetherevenueofInPsandincreasetheutilizationofthesubstratenetworkinthelongrun.
Likethepreviousworkin[28],thelong-termaveragerevenueisgivenbylimT→∞PTt=0R(Gv,t)T.
(3)n1A1D1B1C1A2D2B2C2n2(a)noden1(b)noden2Figure2:MotivationalexampleTheVNRacceptanceratioofthesubstratenetworkcanbedenedbylimT→∞PTt=0VNRsPTt=0VNR,(4)whereVNRsisthenumberofVNrequestssuccessfullyac-ceptedbythesubstratenetwork.
Wealsoconsiderthelong-termrevenuetocostratiotoquantifytheeciencyofresourceutilizationofthesubstratenetwork:limT→∞PTt=0R(Gv,t)PTt=0C(Gv,t).
(5)Ifthelong-termaveragerevenuesoftheVNembeddingso-lutionsareaboutthesame,thehigherVNacceptanceratioandR/Cratioarepreferred.
4.
TOPOLOGY-AWARENODERANKINGVNembeddingincursnodemappingandlinkmapping.
NodemappingcanbeachievedbyselectingsubstratenodeswithsucientCPUresources,andlinkmappingrequiressucientlinkresourceonbothoftheselectednodesandthepathbetweenanytwoselectedsubstratenodes.
Mostearlypublications(e.
g.
,[28])performnodemappingsandlinkmappingsattwodierentstages,wherenodesareselectedrstatthenode-mappingstage,andlinkallocationandpathselectionaredoneatthelink-mappingstage.
Wetakeadif-ferentapproachbyincorporatingtopologyattributesdur-ingthenodemappingstage,aimingtoimprovethesuccessrateandeciencyoflinkmapping.
Amotivationalexam-pleisillustratedinFig.
2,wherelargernodesarenodeswithmoreCPUresourcesandthewiderlinesarelinkswithmorebandwidthresources.
Nodesn1andn2seemtohavethesameresourceavailabilityiftheyareconsideredalone.
However,n1isa"better"nodebecausetheneighborsofn1,namely,A1,B1,andC1,havemoreresourcesthanthoseofn2'sneighbors,andsomappingavirtualnodeton1hasahigherchancetoachieveasuccessfullinkmapping.
Wedenethenotionofnoderanktomeasuretheresourceavailabilityofanode.
Intuitively,therankofagivennodeuisdeterminedbyitsCPUpoweranditscollectiveband-widthofoutgoinglinks.
Itisalsoaectedbytheranksofthenodesthatcanbereachedfromu.
WemodeltherstusingtheproductofitsCPUandcollectivebandwidthofoutgoinglinksasin[28].
Wemodelthesecondbydividingreachablenodesintotwogroups,thatis,thenodesthatareincidenttotheoutgoinglinksfromuandthenodesthatcanbereachedfromuviamultiplehops.
Modelingconnectivityischallenging,andinthispaperwedeneajumpingprob-abilitytomodelthelikelihoodofanodethatisreachablefromuviamultiplehopsanddeneaforwardprobabilitytomodeltheinuenceoftheneighboringnodesfromu'sforwardlinks.
Inparticular,letH(u)=CPU(u)Xl∈L(u)BW(l),(6)where,onasubstratenetwork,L(u)isthesetofalltheoutgoinglinksofu,CPU(u)istheremainingCPUresourceofu,andBW(l)istheunoccupiedbandwidthresourceoflinkl.
Onavirtualnode,CPU(u)andBW(l)aretheca-pacityconstraintsofthenodeu,respectively.
TheinitialNodeRankvaluefornodeucanbecomputedbyNR(0)(u)=H(u)Pv∈VH(v).
(7)Letu,v∈Vbetwodierentnodes.
LetpJuv=H(v)Pw∈VH(w),(8)pFuv=H(v)Pw∈nbr1(u)H(w),(9)wherepJuvdenotesthejumpingprobabilityfromnodeutolandonnodev,nbr1(u)={v|(u,v)∈E},andpFuvtheforwardprobabilityfromnodeutonodevwith(u,v)∈E.
Clearly,Xv∈VpJuv=1,Xv∈nbr1(u)pFuv=1.
TheprobabilitiespJuvandpFuvmaybeviewedasresourcevotingfornodeufrom,respectively,anynodereachablefromuandnodeu'sneighboringnodes.
Thevotingfromanon-neighboringnodeimpliesthatthereshouldexistamulti-hoppathbetweenuandv.
Thus,thetopologyinfor-mationofthetwonodesisalsoembeddedintheprobabili-ties.
Foranynodev∈V,letNR(t+1)(v)=Xu∈VpJuv·pJu·NR(t)(u)+Xu∈nbr1(v)pFuv·pFu·NR(t)(u),(10)wherepJu+pFu=1,pJu≥0,pFu≥0,andt=0,1,ThepJuandpFuarebiasfactors,andwewilltypicallywanttosetpJuto0.
15andpFuto0.
85(fordetailsseeSection6).
ForanetworkofnnodeswithV={v1,v2,vn},letNR(t)i=NR(t)(vi)anddenotethevectorofnoderanksatiterationtbyNR(t)=(NR(t)1,NR(t)2NR(t)n)T,wheret=0,1,WehaveNR(t+1)=T·NR(t),whereTisaone-steptransitionmatrixoftheMarkovchaindenedbyT=0BBB@pJ11pJ12···pJ1npJ21pJ22···pJ2n.
.
.
.
.
.
.
.
.
.
.
.
pJn1pJn2···pJnn1CCCA·0BBB@pJ10···00pJ2···0.
.
.
.
.
.
.
.
.
.
.
.
00···pJn1CCCA+0BBB@0pF12···pF1npF210···pF2n.
.
.
.
.
.
.
.
.
.
.
.
pFn1pFn2···01CCCA·0BBB@pF10···00pF2···0.
.
.
.
.
.
.
.
.
.
.
.
00···pFn1CCCA(11)NotethatTisstablesinceitisastochasticmatrixhav-ingamaximumeigenvalueequaltoone.
ThisguaranteesthattheaboverecurrencerelationconvergestoNR()=(NR()1,NR()2NR()n)T,thesteadystatedistribution[25].
Thiscanbecomputedusingaclassiciterativescheme[23],givenbyAlgorithm1.
Algorithm1TheNodeRankComputingMethod1:Givenapositivevalue,i←02:repeat3:NR(i+1)←T·NR(i)4:δ←NR(i+1)NR(i)5:i++6:untilδAmazonec2,http://aws.
amazon.
com/ec2/.
[2]VNE-RWSimulatorhttp://int.
bupt.
edu.
cn/sensu/vne-rw.
html.
[3]VNESimulatorhttp://www.
cs.
princeton.
edu/minlanyu/embed.
tar.
gz.
[4]R.
K.
Ahuja,T.
L.
Magnanti,J.
B.
Orlin,andK.
Weihe.
Networkows:theory,algorithms,andapplications.
PrenticehallEnglewoodClis,NJ,1993.
[5]DavidG.
Andersen.
Theoreticalapproachestonodeassignment.
UnpublishedManuscript,December2002.
[6]M.
Bianchini,M.
Gori,andF.
Scarselli.
Insidepagerank.
ACMTransactionsonInternetTechnology(TOIT),5(1):92–128,2005.
[7]N.
Butt,M.
Chowdhury,andR.
Boutaba.
Topology-AwarenessandRe-optimizationMechanismforVirtualNetworkEmbedding.
InNetworking2010:9thInternationalIpTc6NetworkingConference,Chennai,India,May11-15,2010,Proceedings,page27.
NotAvail,2010.
[8]N.
M.
M.
K.
ChowdhuryandR.
Boutaba.
Networkvirtualization:stateoftheartandresearchchallenges.
IEEECommunicationsmagazine,47(7):20–26,2009.
[9]N.
M.
M.
K.
Chowdhury,M.
R.
Rahman,andR.
Boutaba.
Virtualnetworkembeddingwithcoordinatednodeandlinkmapping.
InIEEEINFOCOM,2009.
[10]L.
P.
Cordella,P.
Foggia,C.
Sansone,andM.
Vento.
Animprovedalgorithmformatchinglargegraphs.
In3rdIAPR-TC15WorkshoponGraph-basedRepresentationsinPatternRecognition,pages149–159,2001.
[11]M.
Diligenti,M.
Gori,M.
Maggini,andD.
diIngegneriadell'Informazione.
Auniedprobabilisticframeworkforwebpagescoringsystems.
IEEETransactionsonknowledgeanddataengineering,16(1):4–16,2004.
[12]D.
Eppstein.
Findingthekshortestpaths.
InProc.
ofIEEESymposiumonFoundationsofComputerScience.
IEEEComput.
Soc.
Press,1994.
[13]J.
FanandM.
Ammar.
Dynamictopologycongurationinserviceoverlaynetworks:Astudyofrecongurationpolicies.
InProc.
IEEEINFOCOM,2006.
[14]N.
Feamster,L.
Gao,andJ.
Rexford.
HowtoleasetheInternetinyoursparetime.
ACMSIGCOMMComputerCommunicationReview,37(1):64,2007.
[15]GlobalEnvironmentforNetworkInnovations.
NationalScienceFoundation,http://www.
geni.
net/,August2005.
[16]M.
Gori,M.
Maggini,andL.
Sarti.
Exactandapproximategraphmatchingusingrandomwalks.
IEEETransactionsonPatternAnalysisandMachineIntelligence,27(7):1100–1111,2005.
[17]C.
Guo,G.
Lu,H.
J.
Wang,S.
Yang,C.
Kong,P.
Sun,W.
Wu,Y.
Zhang,MSRAsia,andMSRRedmond.
SecondNet:ADataCenterNetworkVirtualizationArchitecturewithBandwidthGuarantees.
[18]A.
Gupta,J.
Kleinberg,A.
Kumar,R.
Rastogi,andB.
Yener.
Provisioningavirtualprivatenetwork:Anetworkdesignproblemformulticommodityow.
InProceedingsofthethirty-thirdannualACMsymposiumonTheoryofcomputing,pages389–398.
ACMNewYork,NY,USA,2001.
[19]J.
He,R.
Zhang-Shen,Y.
Li,C.
Y.
Lee,J.
Rexford,andM.
Chiang.
Davinci:Dynamicallyadaptivevirtualnetworksforacustomizedinternet.
InProceedingsofthe2008ACMCoNEXTConference,pages1–12.
ACM,2008.
[20]I.
Houidi,W.
Louati,andD.
Zeghlache.
Adistributedvirtualnetworkmappingalgorithm.
InProceedingsofIEEEICC,pages5634–5640,2008.
[21]J.
LischkaandH.
Karl.
Avirtualnetworkmappingalgorithmbasedonsubgraphisomorphismdetection.
InProceedingsofthe1stACMworkshoponVirtualizedinfrastructuresystemsandarchitectures,pages81–88.
ACM,2009.
[22]J.
LuandJ.
Turner.
Ecientmappingofvirtualnetworksontoasharedsubstrate.
DepartmentofComputerScienceandEngineering,WashingtonUniversityinSt.
Louis,TechnicalReportWUCSE-2006,35,2006.
[23]L.
Page,S.
Brin,R.
Motwani,andT.
Winograd.
Thepagerankcitationranking:Bringingordertotheweb.
Technicalreport,StanfordDigitalLibraryTechnologiesProject,1998.
[24]R.
Ricci,C.
Alfeld,andJ.
Lepreau.
Asolverforthenetworktestbedmappingproblem.
ACMSIGCOMMComputerCommunicationReview,33(2):81,2003.
[25]E.
Seneta.
Non-negativematricesandMarkovchains.
SpringerVerlag,2006.
[26]W.
Szeto,Y.
Iraqi,andR.
Boutaba.
Amulti-commodityowbasedapproachtovirtualnetworkresourceallocation.
InProc.
GLOBECOM:IEEEGlobalTelecommunicationsConference,2003.
[27]JSTurnerandDETaylor.
Diversifyingtheinternet.
InIEEEGlobalTelecommunicationsConference,2005.
GLOBECOM'05,volume2.
[28]M.
Yu,Y.
Yi,J.
Rexford,M.
Chiang,etal.
Rethinkingvirtualnetworkembedding:Substratesupportforpathsplittingandmigration.
COMPUTERCOMMUNICATIONREVIEW,38(2):17,2008.
[29]Y.
ZhuandM.
Ammar.
Algorithmsforassigningsubstratenetworkresourcestovirtualnetworkcomponents.
InProc.
IEEEINFOCOM,2006.