网络编码能够提高吞吐量吗？

DoesNetworkCodingimprovetheThroughputofa

SurvivableMulticastNetwork?

SourourElloumi

CEDRIC-ENSIIE

Evry,France

Email:sourour.elloumi@ensiie.fr

Abstract—Weaddresssurvivabilityconsiderationsfortelecommunicationnetworkswhereapartofthenetworkmay

fail.Wefocusonsinglearcfailuresinmulticastnetworks,

withorwithoutnetworkcoding.Theproblemistocomputea

routingsuchthat,ifanysinglearcfailureoccurs,theremaining

throughputisaslargeaspossible.Inthecaseofmulticast

routingwithoutnetworkcoding,twowaysforcomputingthe

impactofanarcfailureareconsidered.Eitherthethroughput

ofentireSteinertreescontainingthatarcvanishes,oronlythe

throughputofsubtrees,startingfromthatarctoterminals,is

discarded.Inthecaseofmulticastwithnetworkcoding,sincethe

totalthroughputiscomputedastheminimumofsinglemax-?ow

valuesfromthesourcetoanyterminal,weconsiderthatafailure

ofanarcimpliesthatthethroughputofallpathscontaining

thatarcvanishes.Thethreeobtainedmodelsareformulated

aslinearproblems.Wesolvetheseproblemseitherdirectlyor

byuseofcolumngeneration.Further,thesurvivablenetwork

codinggainisde?nedastheratioofmaximalthroughputwith

-overwithout-networkcoding,whenarcfailurescanoccur.

Weshowthatthisratioisunboundedforunitarycombination

digraphsandhenceforanydirectednetworks.Wealsoshow

thatthisratioisequaltooneforbidirectedgraphswithuniform

capacities.Finally,somenumericalresultsarecarriedouton

randomlygeneratednetworksshowingthatthegainratiois

equaltooneforalmost98percentoftheinstances.However,

weobservethatroutingwithnetworkcodingrequiresmuchless

redundancyinordertoachievetheoptimalthroughput.EricGourdinandThibautLefebvreOrangeLabs,NMP/TRMIssy-les-Moulineaux,FranceEmail:(eric.gourdin,thibaut.lefebvre)@http://wendang.chazidian.comcompletely[5](inotherwords,thereisnobene?ttousenetworkcodinginsteadofmulticastinbidirectednetworks).Beyondthesetheoreticalbounds,severalpapershaveanalyzedthepracticalgainsobservedoverseriesofnumericalinstances[6],[7].Itappearsthat,inpractice,forthevastmajorityofrandomlygeneratedinstances,thereisnothroughputgain.Notehoweverthat,onlargerinstances,thenumberofmulticasttreesrequiredtoachievethemaximumthroughputcanbecomequitelarge.Inbackboneandwiredaccessnetworks,failuresofequip-ments(routers,linecards,etc...)areoftenobservedandtheroutingprotocolsaredesignedtoovercomethesetemporary(butsometimeslonglasting)situations.Onequestionthatnaturallyarisesiswhethernetworkcodingcouldbeusedtoimprovethroughputinnetworkspronetocongestionsorevenfailures.Amongtheintensiveresearchdevotedtonetworkcod-ing,signi?canteffortshavebeenspenttoanalyzetheimpactofnetworkcodinginlossynetworks[8],[9]resultinginrealimplementations.Forinstance,CodedTCP[10]wasshowntoimprovespectacularlytheperformancesinheavilycongestedTCPnetworks.Severalpapersaddresstheissueofrobustnetworkcoding,namelyacodingschemethatremainsvalid(allterminalnodesarestillabletodecode)forallconsideredfailurepatterns.In[11],theauthorsshowthereexistsalinearcodingschemeprovidedthesizeofthe?nite?eldisincreasedandin[12],polynomialalgorithmsareprovidedtocomputesuchcodes.Boundsonthenumberofcodesrequiredinvariousfailurescenariosaregivenin[13].

Inthispaper,wepreciselyaddressthecomplementaryissueofanalyzing,withtheoreticalandnumericalarguments,thenetworkcodinggaininamulticastnetworkwheresinglearcfailurescanoccur.Moreprecisely,weconsidertheoptimiza-tionproblemsof?ndingaroutingparadigm(setsofmulticastrouteswithorwithoutnetworkcodingactivatedatintermediatenodes)suchthatthethroughputismaximizedfortheleastfavorablesinglearcfailurescenario.

Therestofthepaperisorganizedasfollows:InSectionIIwepresentourassumptionsonthefailuresandthewaytheyimpactthethroughput.InSectionIIIwederivethreelinearprogrammingmodelsandweproposesolutionapproachestosolvethem.Wealsofocusontheparticularcaseofasingleterminalnetworkwhereourproblemsspecializetoaproblemofbalancedmax-?ow.InSectionIV,wede?nethesurvivablenetworkcodinggainandweshowthatitisunboundedfordirectednetworks.Wethenprovethatthereisnoadvantageinusingnetworkcodinginuniformbidirectedgraphs.InI.INTRODUCTIONNetworkCodinghasbeenintroducedin[1]asanicemech-anismallowingtoreachatheoreticalupper-boundonmulticastthroughputintelecommunicationnetworks.Themainideaistoallowintermediatenodestoperformcodingoperationsonthedatatheyreceivebeforeforwardingthemtowardstheseveraldestinationnodes.Thebestpossiblethroughputisde?nedastheonethatwouldbeobtainedifeachsource-destinationpairwouldbealoneinthenetwork(singlemaximum?ows)anditisshownin[1]thatnetworkcodingallowstoachieveallthesemaximum?owssimultaneously.Muchefforthasbeenspenttoanalyzefurtherthenetworkcodinggain,de?nedastherelativeincreaseofthroughputofferedbynetworkcodingoverstandardmulticastforwarding.Recently,severalresultshaveestablishedupper-boundsonthisgaininvariouscontexts:fordirectedgraphs,instanceshavebeenbuiltin[2],[3]wherethethroughputgaincanbearbitrarilylarge.Onthecontrary,itwasshownin[4],thatthegainisboundedbyavalueof2inundirectedgraphs.Evenmoresurprising,inbidirectedgraphs(graphswherealinkbetweentwonodesiandjisde?nedbyapairofarcs(i,j)and(j,i)ofsamecapacity),thegainvanishes

978-1-4799-4009-7/14/$31.00 ©2014 IEEE

内容需要下载文档才能查看

Fig.1.Anexampletocomparethemaximum?owwithamaximumsurvivable?ow.

sectionVwegivenumericalresultson500randomlygeneratedinstancesandwedrawsomeobservationsonthein?uenceofnetworkcodingonsurvivability.SectionVIisaconclusion.II.

ASSUMPTIONSREGARDINGTHEIMPACTOFFAILURES

Takingintoaccountfailuresisacentralfeatureoftelecom-municationnetworkdesign.Therearenumerousstrategiesandapproachesproposed,developedandimplementedtoavoidasmuchaspossiblethenegativeeffectsofafailure[14].Broadlyspeaking,theseapproachescanbeclassi?edintotwomainclasses:insomeapproaches(protection),someactionistakenpriortoanyfailureinordertopreserveasmuchtraf?caspossiblefromthefailure,whereasinothers(restoration),theactionistakenafterthefailureoccurs(although,inmostcases,ithasbeencarefullyplanedandprepared).

Inthispaper,wefocusonthe?rsttypeofapproaches:wemaketheassumptionthata?xedrouting/codingpatternhastobede?nedsothat,ifsome(orall)ofthetransmitteddataisreplicated,thecompleteoriginaldatacanstillbereceived(andpotentiallydecoded)byeachterminalnode,whateversinglearcfailureoccurs.Moreprecisely,weconsideroptimizationproblemswherethedataissentalongvariouspathsortrees,potentiallycodedatsomeintermediatenodes,and,theamountoftraf?cstillreceivedbyeveryterminalwhenafailureoccurs,ismaximized.

Whenusingnetworkcoding,weknowthatthethroughputachievedtowardseachterminalnodeisthevalueofthemaximum?owbetweenthesourceandthatterminal[1].Wehencede?nethesurvivablenetworkcodingthroughputasthemaximum?owremainingwhentheworstfailureoccurs(namelythefailureofthearcwherethemaximumamountof?owisrouted).Sincetheproblemcanbedecomposedterminalbyterminal,wearehenceledtoconsideravariantofthemaximumsingle?owproblemwithasurvivabilityconstraint[15].ConsiderforinstancethesimpleexampleofFigure1:thevalueofamaximum?ow,30,isreachedattheminimumcutδ+maximum(s).?owHowever,valuedropswhentooneofthearcsisremoved,the?15.Thisvalueisobtainedwhenconsideringthetwoarcsinδroutedthroughthetwoarcs.If(wet1):sendthetotal18on?owtheofupper30mustarcandbe12onthelowerarc,theniftheupperarcfails,only12unitsof?owremain.Thesolutionthatmaximizestheremaining?owforeveryfailureistosend15unitsonbotharcs.

Multicastroutingisbasedonmulticasttrees[16].Thereareseveralswaystomodeltheimpactofanarcfailureonamulticasttree:eitherthemulticasttreesaremanagedandmonitoredbyacentralentity,ortheyareobtainedastheresultofadistributedprocessandhenceadapttoevolvingnetwork

Fig.2.Impactoffailuresonamulticasttree.

Fig.3.Thenetwork(a)hasacentralsourcenodesandthreeterminalstandt1,t23.Eachdirectedarchasacapacityofoneunit.Anetworkcodingsolutionisdepictedin(b):eachterminalreceivestwostreamsofoneunitandishenceabletodecodethestreamsAandB.

conditions.Asaconsequence,weproposetoinvestigatetwosurvivablemulticastmodels:(i)amodelwhereawholemul-ticasttreeisdis-activated(itcannotcarryanymoretraf?c)assoonasoneofitsarcshasfailed,and(ii)amodelwherethesubtreethatstillconnectsthesourcetosometerminalremainsactivewheneveranarcfails.IntheexampleofFigure2,thearc(a,d)belongstothetree.Theimpactofthefailureofthisarccanbe:(i)eitherthewholemulticasttreeisdiscardedor(ii)onlythesubtree{(a,d);(d,tstillbesentfromthesourcenode1)}sistowardsdiscardedthebutterminalsdatacantandt.Thefailureofarc(b,e)hasclearlynoimpact.23Aswewillsee,the?rstsurvivablemulticastmodelismorerestrictivethanthesecond,whichisstillmorerestrictivethananetworkcodingmodel(whichachievesthebestpossiblethroughput)http://wendang.chazidian.comingthefundamentaltheoremin[1],itiseasytoseethat,whateversinglearcfailureoccurs,amaximum?owofoneunitcanstillreacheachterminal.Notehoweverthatthislastpropertyisnecessarybutnotsuf?cientinorderforaterminaltoactuallydecodereceivedinformation.ConsiderforinstancewhathappensonFigure3atterminalt).Thisissuewillbeaddressed2ifarc(s,b)failsinsteadofarc(s,ainsectionIII.C.ThesurvivablethroughputachievedwithbothmulticastmodelsisillustratedinFigure4:the?gureshowsavalidmulticastsolutionmadeof6differentmulticasttrees,eachonecarryinga?owof1/4units.Withthe?rstmodel,whenanyoneofthecentralarcs(theonesconnectedtothesource)fails,fouroutofthesixtreesalsofailandcannotcarryanytraf?c.Thetworemainingtreesallowtosend1/2unittowardseachterminal.Withthesecondmulticastmodel,whenthesametypeoffailureoccurs,sayforinstancethearc(s,a),thetreeτ1,τ4,τ5andτ6canstillbeusedtosendtraf?ctowardsterminalt1.TableIsummarizes,foreacharcfailure,the?owreceivedbyeachterminal.

Weseethattheminimumthroughputthatcanbeguaran-teedtowardseveryterminalwiththesecondmulticastmodel,

arcfailedt(13t23t3((s,s,bc))3/3/33/(a,3/43/423/4(a,

t2)3/243/23/42(b,tt3)1)3/23/4(b,3/43/23/2(c,t2)c,t

t1)3/23/23/23)3//423/43//223//24

TABLEI.

FLOWRECEIVEDBYTERMINALSFOREACHARCFAILURE

(GRAPHOFFIGURE

3)

Fig.4.OnthesamedirectedgraphasinFigure3,asetofsixmulticasttreesthatconstituteanoptimalsolutionofbothsurvivablemulticastthroughputproblems,whencarryinga?owof1/4unitseach.

intheworstfailurecaseis3/4.

Wewillnowshowhowtheseproblemscanbeproperlymodeledandproposesomeresolutionapproaches.

III.

MODELSFORTHESURVIVABLETHROUGHPUT

Givenamulticastnetwork,weareinterestedincomparing

thethroughputachievedwhileusingornotnetworkcodingmechanisms.Contrarytopriorwork,wealsoconsiderthatthenetworkispronetofailures.Werestrictourattentiontothemostfrequenttypeoffailure,namelythefailureofasinglelinkatatime.

WewilldescribeourmodelsinthesettingofadirectedgraphD=(V,A)whereVisthesetofnodesandAisthesetofarcs.Notehoweverthatmostofthemodelscaneasilybeadaptedtothecaseofundirectedorbidirectednetworks,andcanhencebeusedforcomputingthroughputvaluesinthesevarioussettings.

ForeacharcainA,wedenotebyCWeconsideramulticastsessionoriginatinga∈Zfrom+itscapacity.asourcenodesinVandsimultaneouslyroutedtowardsasubsetTofV\{s}whoseelementsarecalledclientsorterminals.Severalmodelshavebeenproposedtocomputethemaximum

throughputinthenominalstate(withoutfailures).Tothebestofourknowledge,noonehasyetaddressedtheproblemwherefailurescanoccur.

A.Firstsurvivablemulticastmodel:discardingwholetreesWe?rstconsiderthefollowingsurvivablemulticastthroughputproblem:?ndasetofmulticasttreesandassignathroughputtoeachtreesothat(i)thesumofthroughputvaluesoneacharcdoesnotexceedthecapacity,and(ii)thetotalthroughputachievedintheworstfailurestate,ismaximized.Ingeneral,afailurestatecanbemodeledasasubsetofnetworkelements(nodesand/orarcs)thatarepronetofailsimultaneously.Wemodelthefailurebyremovingthoseelementsfromthegraph.WedenotebyFthesetofallfailuresstates.Inthispaper,wewillrestrictourattentiontothefailurestatesconsistingofallsinglearcsF={{a};a∈A},or,withaslightabuseofnotation,F=A.Wesupposethattherearetwoarc-disjointpathsbetweenthesourcesandeachterminaltinourgraphsothatthedeletionofanysinglearcstillallowstheroutingofinformationfromstot.However,sincethisproblemcaneasilybemodeledinthegeneralcase,inthissection,wewillassumeanypotentialfailuresetF.Inthis?rstmodel,themulticastthroughputinthepresenceoffailures(modeledbyF)isthenobtainedbyremoving,foreachfailurestatef∈F,allthecorrespondingnodesandarcsandallthetreesintersectingatleastoneelementofeachf.Theresultingfailurethroughputisthenthesumofthroughputoftheremainingtrees.WedenotebyT(s,T)(orsimplyTwhentheparametersareclearfromthecontext),thesetofdirectedtrees(arborescences)fromstoT.Let?.Wenowintroducethesetofτbetheamountof?owontreeτfeasiblemulticastroutingsΩmc?:

?Ωmc

=?????(???τ)τ∈T|

a∈A,?≥0??τ≤Ca?(1)τ?a∈T

∈τ

?wherewehavestandardcapacityconstraints.Denotebyv(?)thesumofthroughputsor?owscarriedbythetrees:

v(?)=

??

?τ(2)τ∈T

Alsodenotebyvputcarriedbytreesf(?intersecting)(resp.v(?(resp.))thenotshareintersecting)ofthisthrough-someelementsoff.Wearereadytoexpressthe?rstmodelMC1whichconsistsinmaximizingoverallvalidmulticastroutingFpatternstheminimumresidualthroughputsetf∈Ffails.Wedenotebyλmc1

obtainedwhenany

thecorrespondingsurviv-ablemulticastthroughput(optimalF

valueofthisproblem):

λmcF

1=?max∈Ωmcminf∈F{??v(?)?????vf(?)}??

(3)

v(?)

Thisproblemcanalsobeexpressedbyusinglinearprogram-ming:

?

????max??λ,(4)

??

?τ≥λ?f∈F

(5)MC1F

?τ∈T

??f∩τ=????

?∈Ωmc(6)λ≥0

(7)

Constraints(5)statesthat,λ,thevariablewearemaximiz-ing,islessthanthethroughputcarriedbythesetoftreesstillactivewhenthesetf∈Ffails.

Notethat,inthecasewhereF={?},improperlyF=?,themodelMC?,orMCforshort,isnothingelsethanthefractionalSteinertreepackingmodeloftenused(seeforinstance[17],[18],[7])toobtaintheusual(failure-free)multicastthroughput.Wedenotebyλmc,insteadofλmcnominalmulticastthroughput(optimalvalueofMC).?,theWhenF=Awe??

canexpressconstraints(5)as

?τ≥λ?a∈A

(8)

τa∈T∈τ

ItfollowsthatwecansolveMC1techniques,awell-knownoptimizationAbyusingcolumngeneration

approachwherevari-ablesareprogressivelyintroducedaccordingtotheirreducedcost.Denotingbyμthevectorofdualvariablesassociatedtoconstraints(8)andbyνtheoneassociatedtocapacityconstraintsin(1),thereducedcostofeachvariable?τisthen:

r1??τ=μ????a?νa=Υ1

?(μa+νa)(9)whereΥ1=??

a∈/τa∈τa∈τ

a∈Aμa.Thepricingproblem(?ndthevariable

ofmaximumreducedcost)isastandardminimumcostSteinerarborescenceproblem:

min

??

τ∈T

(μa+νa)(10)a∈τ

Weuseaclassicalmixed-integermodel[19],[20]tosolvetheSteiner?

arborescenceproblem:

????min??(μ?a+νa)xa,(11)???a∈A??????t??

t

??f11ififvv==st?v,?a?fa=

t(12)???a∈δ?(v)a∈δ+(v)0otherwise???fa

t≤x?a,t(13)fat

a∈{0,1}?a,t(14)If,bysolvingthisproblem,we?ndatreewithapositive

reducedcost,thistreerepresentsanewcolumntobeaddedtothemasterproblem,whichisthensolvedagain,etc.Ifwearenotabletoexhibitsuchatree,thenitmeansthatwehaveobtainedanoptimalsolution.Thisisthetechniquewehaveusedinourexperimentalsetting.

B.Secondsurvivablemulticastmodel:discardingsub-treesInthissecondmodel,weconsiderthatafailuredisconnectssometrees,butthesub-treesstillconnectingthesourcetosometerminalscanbeusedtosend?ow.ForthesakeofbrevitywewilldirectlydescribethemodelforthecaseF=A.Tode?nethismodel,weneedtheadditionalnotationpstbetweensandtintreeτ.Theτforthe(unique)directedpathsecondmodelMC2Acanthenbeformulated?asfollows:

???λmc??

??A2

=?max

∈Ωmcmina∈Amint∈T??v(?)??τ(15)aτ∈∈T

?pst?τ

Inotherwords,weseekanassignmentof?owsontreessuchthat,removinganyarca,theminimumamountof?owthatcanstillbesenttoanyterminalismaximized.Asforthepreviousmodel,MC2Acaneasilybelinearizedendingupwithalinearprogrammingmodelinvolvinganon-polynomialnumberofvariables.

Notethatthisformulationcontainsagaincapacitycon-straints(withassociateddualvariablesνconstraintsforeachfailurea∈Aandeacha)andthroughputterminalt∈T(withassociatedvariablesμta).Acolumngenerationapproachisstillpossible.However,thepricingproblemisdifferent.Indeed,thereducedcost?

associatedtoeachtree?τbecomes:

r2

τ=Υ2??????

μt??a+νa?,(16)????t∈Ta∈pstτ

a∈τ

whereΥ2t

in?nding=t∈aTSteinera∈Aμarborescencea.Thepricingproblemthenconsistsτminimizingtheexpressionbetweenparenthesesin(16).Changingtheobjectivefunction(11)into

min

????

μt??afat+νaxa,(17)a∈At∈T

a∈A

inthepricingproblemforMC1thesolutionsprovidedA(andaddingafewconstraints

toensurethatareindeedtrees)yieldsavalidformulationforthisnewpricingproblem.

Observethatsinceforanarca∈Aandaterminalt∈Twehave??

?≤??τ?τ(18)

aτ∈∈T

pstτa∈T

τ

∈τ

anoptimalsolutiontoproblemMC1MC2

AisfeasibleforproblemA,andhence

λmcA1≤λmcA2(19)C.Thesurvivablenetworkcodingthroughput

Similarly,theSurvivableNetworkCodingproblemNCconsistsin?ndingacoding/routingpatternsuchthattheF

throughputobtainedintheworstfailurecaseismaximized.For

aterminaltletPstbethesetofpathsthesourcesWewillalsousethesetP=??betweenandt.offeasibletnetwork∈T.Thosecodingnotationsroutingallowt∈Tst

ΩncusPofpathsbetweensandanytointroducetheset?:

?Ωnc

=????(????A,t∈T,?≥0

?p)p∈P|?p≤Ca?a∈p∈Pst??a∈p

st

(20)

Denotebyv(?sandtandbyv)(the?sttotal)andvaluevofthe?owsentbetweenfroutedrespectivelythrough(?st)thesharesofthe?ow?stfailedelementsornot,thenproblemNCFcanbeexpressedλnc??as:

F=st???max∈Ωncminf∈Fmint∈T??v(?)?vf(?st

)??

(21)v(?st)

whereλncFisthesurvivablenetworkcodingthroughput.Thisde?nitionreliesontheexistenceofacodingscheme

whichisgivenbytheorems11and12in[11].Theorem11

statestheexistenceofacommonlinearcodingschemetoallarcfailuresprovideditisstillpossibletosendinformationtoeachterminalifanyarcfails.Theorem12givesaboundonthesizeofthe?nite?eldwhichisusedtoperformlinearcodingoperations.

Again,wecanexpressthisproblemvialinearprogram-ming:

?

????max(22)

????λ,?p≥λ?f∈F,t∈T

(23)NCF

?p∈Pst??f∩p=?

???

?∈Ωnc(24)λ≥0

(25)

Again,notethatNC?,orNCforshort,isastandardmodel(writtenwithpath-?owvariables)fortheusual(failure-free)networkcodingthroughput.Wedenotebyλnc,insteadofλncnominalnetworkcodingthroughput.

?,theNotethatarc-?owmodels(involvingtheso-called?owconservationconstraints)couldbeusedeitherforNCForNC.Ifwedenoteby?sthavetheathe?owbetweensandtcarriedbyarca,thenwefollowingrelationbetweenthetwomodels:

?sta

=???p?a∈A,t∈T(26)p∈Psta∈p

:

Moreover,asforNC,problemNC?owproblems.AreducestoasetofindependentsingleLemma1.

????

λncA

=mint∈T?max∈Ω

nc

v(?st)?maxa∈A

?sta(27)

Proof:introducingathroughputvariableλtforeachterminalt∈T,problemNCAcanberewritten:

λnc??A=?max∈Ψ

nc

λ:λ≤λt,?t∈T??(28)whereΨncistthesetofconstraints(23)-(25)whereλis

replacedbyλin(23).Itthensuf?cestoseethatthisconstraintsetcanbefullydecomposedbyterminalleadingtoabloctriangularstructureandhence:

????

λncA=maxλ

λ:λ≤max?t,λ

t

λt,?t∈T(29)andtheresult

follows.

SincewecandecomposeproblemNCAinto|T|inde-pendent?owproblems,itisusefultostudytheinduced

single?owproblem.Considerasingles-t?ow.Sinceweareonlyconsideringasinglecommodity,wewillomitthesuperscriptst.Themaximumarc-balanced?owproblemisthespecialcaseofproblemNCcase,SteinerAwhereonlyoneterminalnodeisconsidered.Inthistreesareexactlypathsbetweenthesourceandtheterminal,andthereforemulticast

TABLEII.

NETWORKCODINGGAININNOMINAL(FAILUREFREE)

CASE

Bidirected?uvuv

Undirected

uv?≤Cuv,CuvC=Cvu

θuv+?vu≤[uv]θ=≤12[4][5]

andnetworkcodingareequivalent.WedenotethisproblembyMFA:

MFA:λA

=?max∈Ωstamin??∈A{v(?)??a}

??(30)=

?max∈Ω

st

v(?)?maxa∈A

?a(31)

withsimilarnotationsasbefore,namelyΩstisthesetof

feasibles-t?ows,v(?)isthevalueofthe?owand??owonarca.

aistheLemma2.Thereisanoptimalsolution??ofMFforMF(i.e.,??isamaximums-t?ow).AthatisalsooptimalSee[15]forastudyofproblemMF2.ByusingthislemmawecanAincludingaproofofLemmainterpretourproblemMFAinthefollowingmanner:wearelookingforamaximumsthrough-t?owansucharcofthatthethenetworkmaximumisminimized.

amountof?owpassingIV.

THESURVIVABLENETWORKCODINGGAIN

nc

Thenetworkcodinggain,de?nedastheratioθ=

λdirected,/λmc,hasbeenconsiderablystudied:theboundsobtained(inundirectedandbidirectedgraphs)aresummarizedinTableII.Notethatθisalwaysnolessthanonesincemulticastroutingisaspecialcaseofnetworkcodingroutingwithoutcodingatintermediatenodes.

Weareinterestedinevaluatingthesurvivablecodinggainde?nedas:θ1toseetowhatextentresultsA=obtainedλncA/λmcA1andθ2network

forθremainA=validλncA/λmc2orA

notincasewherearcfailurescanoccur.Observethatanoptimal

solutiontoMC1AorMC2

AgivesusafeasiblesolutiontoNCthereforewehave,again,thatforanynetwork,θ1Aandθ2

areA

nolessthanone.

AA.Thesurvivablenetworkcodinggainisunboundedfordirectedgraphs

The?rstresultisthatthegainremainsunbounded(inthecaseofarcfailure)fordirectedgraphs.Toshowthisresult,weusethelayeredcombinationnetworkproposedin[2]andgeneralizedin[3]and[5].Giventwopositiveintegersnandk(with2≤isV,decomposedA)(seeFigurek≤n?1,thecombinationnetworkC(n,k)=into5)threeisde?nedlayers:asVfollows:={s}the∪Iset∪Tof.nodesLayer1containsasinglesourcenodes,layer2containsnnodes,Icontains={1,...one,noden},andforeachlayersubset3isofthesetofterminalswhichIdecomposed;|t|=k}(T??n

??kelementsofI,T={t?intocontainstwosubsets:henceA=kterminals).ThearcsetisA12∪A23.ThereisonearcfromthesourcestoeverynodeinI,AanarcfromanyintermediatenodeinI12to=any{(s,nodeu)|uin∈TI}andFinally,weassumethegraphhasunitcapacities:u,t)∈I×CT|uwhichcontainsthisintermediatenode,A23={(∈t}.eacharcainA.

a=1for