PresenceofHeterogeneousStreams
ShekharSrivastava,DeepMedhiandAppievandeLiefvoort
ComputerScience&ElectricalEngineeringDepartmentUniversityofMissouri-KansasCity,KansasCity,MO
differentAbstract—Differentmulti-mediatrafficsourcescanhaveofissuewhethertrafficcharacteristicswhichcanraisetheissueinmadeabecomestomultiplex(someof)thesesources.Thisbackboneevennetworkmoreimportantintrafficengineeringconstraintsonwhichwhenadecisionneedstoberequirementsontunnelingsourcestomultiplexwhenthereareastreamsmeasureoffordistortiontunnels.andIncapacityalongwithroutingbetweenthispaper,wefirstpresentfactortheinandtrafficshowengineeringtheireffectiveness.twoofbackboneNextdifferentweusetrafficthispresentingpresenceoftunnelingandcapacityconstraintsnetworksinawheretwoanoptimizationformulation.Wethenpresentbytwothesubproblemsinphasetheheuristicfirstandphaseapproachinthethesecondproblemtosolvephaseisdecoupledthisproblemweshowhowintobepresentsimplifiednon-linearproblem(foroneofthesubproblems)canapproachnumericaltodevelopaduality-basedmethod.Wethentohelpsresultstoshowwhereandhowourcapacitymultiplexdependingindeterminingonwhetherwhentheandtunnelingwhichsourcesand/orming/Optimization,IndexconstraintTermsisdominant.—MathematicalProgram-constraint,CorrelatedTrafficTraffic,LagrangianEngineering,Decomposition.
TunnelingI.INTRODUCTION
Packetleveltrafficfordifferentapplicationstendtohavedifferentcharacteristics.Thisfacthasbeenobservedforemergingapplicationssuchasvideoconferencing,peer-to-peer,multimediaapplications[2],[3],[6],[15].Moreover,trafficgeneratedbysuchheterogeneoussourcesaremultiplexedtogetherandsharethesameserverorlink.Whentrafficofdifferentcharacteristicsaremultiplexedtogether,trafficdistortioncanoccurthatcanbesignificantdependingonthechar-acteristicsoftheinputsources[17],[10].Forexample,
ThisworkhasbeensupportedinpartbyNSFgrantANI-0106640.dmedhi@umkc.edu
CorrespondingAuthor:Tel:+18162352006,e-mail:suchimpactscanbefairlystrongwhenoneormoreofthemarecorrelatedinnature.
Inordertominimizedistortion,apossibleapproachwouldbetomultiplex“like-minded”sourcesintodiffer-entstreamswhereeachstreamistunneledseparately.Suchtunnelscanavoidinter-tunneldistortionifthenetworkhasthecapabilitytodoso.Forthispurpose,weconsideranMPLS(multi-protocollabelswitching)net-workwheretrafficofdifferentcharacteristicsareoffered.MPLSallowslabelswitchedpath(LSP)tunnelstobesetupbetweensourceanddestinationnodes;suchtunnelscanbeusedfor“like-minded”sources.Atoneextreme,justonetunnelcanbesetupforallheterogeneoussourceswhichaddstodistortion.Ontheotherextreme,wecanconceivablysetupaseparatetunnelforeachpossiblesourcetoavoiddistortion;thedifficultywiththisscenarioisthatthenumbertunnelscanbeprohibitivelylargethatcannotonlyslowdownprocessingatanMPLSnetwork,butalsocanbeadministrativelydifficulttomanageinanetworksetting.Ourworkismotivatedbythetrafficengineeringissueofthetrade-offbetweendistortionandlimitingthenumberoftunnels,especiallyinanetworksetting.
Thecontributionofthepapercanbesummarizedasfollows.Wefirstpresentadistortionmetricwhichcapturesthedistortionsufferedbyasteamwhensharingaserverwithanotherstream.Themetricisderivedusingthequeueingmodelpresentedin[17],[10].Next,usingthismetric,weconstructanoptimizationformulationwhichminimizesthedistortionsufferedbyindividualstreamsfordifferentsource-destinationnodeswhilere-strictingthemaximumnumberofallowedtunnelsonalinkwhilekeepinginmindcapacityconstraint.Theformulationisgeneralinthesensethatitistransparenttothemethodusedtocomputethevalueofdistortionmet-ric.Theexactformulation(shownbelow)isnon-linearinnatureandhasalargenumberofbinaryvariablesandconstraints;tosolvethisformulation,wepresentatwophasesolutionapproach.Inthefirstphase,wedecouple
theproblemintotwoseparateformulationsandmakeitpossibletoavoidthenonlinearityintheobjectivefunc-tion.Inthenextphase,weuseaLagrangianrelaxationbasedapproachtosolvetheformulation.Themethoddecomposestheproblemintosmallercomponentsandarrivesatthesolutionbyiterativelysolvingthesmallercomponentsandupdatingthedualusingsubgradientoptimization.Usingnumericalresults,wedemonstratetheutilityoftheformulationtowardsallocatingstreamstotunnelswhileminimizingthedistortionsufferedbytheindividualstreams.Wealsoshowthatthecapacityandtunnelingconstraintscoupletogethertoeffecttheoverallflowcarriedandtheoveralldistortionsuffered.Animportantquestioniscollectionofdatafordiffer-enttrafficsourcestodeterminefirstandsecondorderstatistics,forexample,tostudycategorizationofdistor-tion.Thisishoweveroutsidethescopeofthispaper.Inotherwords,wefocusonthefactthatgivendifferenttrafficsourceswithdifferentcharacteristics,howdowebalancebetweenminimizingdistortion,thelimitationonnumberoftunnelsandcapacity.
Therestofthepaperisorganizedasfollows.InsectionII,wepresenttheframeworkusedtocapturedistortionssufferedbythestreamssharingatunnel.InsectionIIIwepresenttheformulationasanquadraticintegerprogrammingproblem.InsectionIV,wepresentoursolutionapproachwhichdecouplesanddecomposestheproblemintosmallerproblems.InsectionV,wepresentanddiscussnumericalresults.WeconcludeinsectionVI.
II.FRAMEWORK
FOR
destination.Allpacketsofatrafficstreamassumetofollowthesamepath.Here,thefirst-andsecond-ordercharacteristicsofatrafficstreamarespecifiedbythemean,andeitherthesquaredcoefficientofvariationformarginalsorthecorrelationdecay(orboth)asthesecond-orderparameterintheconstructionofthearrivalprocesses.Wewillfirstbrieflyreviewthemodelpresentedin[17],andthendiscussimpactofmultiplexingusingthismodeltodetermineadistortionscore.
A.ConstructionofStreams
Inthissection,wereviewtheconstructionoftheinterarrivalprocessofpacketsofthestreamwithagivenfirstandsecondorderstatistics.SincewefollowLinearAlgebraicQueueingTheory(LAQT)representation[9],wefirstbrieflyreviewLAQTdefinitionsandnotations.Amatrixexponential(ME)distribution[9]isdefinedasaprobabilitydistributionwhosedensitycanbewrittenas
(1)
DISTORTION
Inthissection,wepresentawaytocapturedistortionsinducedinatrafficstreambyotherstreamswithwhichitismultiplexed.Ourdiscussionhereisextendedfromamodelpresentedin[17].Weconsiderasingleserver
Departing q packets
(Source q)
µ
νν
(Source p)
q
whereisthestartingoperatorfortheprocess,istheprocessrateoperator,andisasummingoperatorconsistingofavectorofall1’s.Themomentofthematrixexponentialdistributionisgivenby
,whereistheinverseof.Theclass
ofmatrixexponentialdistributionsisidenticaltotheclassofdistributionsthatpossessarationalLaplace-Stieltjestransform.Assuch,itismoregeneralthanthecontinuousPhasetypedistribution.
Thejointdensityfunctionofthefirst-successiveeventintervalsdescribesamatrixexponentialprocess(MEP):
exp
exp
p
Departing p packets
Fig.1.Diagramofthemultiplexerunderconsideration
sharedbetweentwotrafficstreams(and).Atrafficstreamisunderstoodashavingasourceandadestinationwherethesourcegeneratespacketsbasedonthearrivalprocess,whicharecarriedbythenetworktotheintended
(2)
where,thematrixistheeventgeneratormatrix.Ex-amplesforsuchprocessesareaPoissonprocess(=[],=[]),arenewalprocess(therankofis1,=
),andaMarkovArrivalProcesses(MAP).NotethatandarenotlimitedtobeingMarkovianratematrices,sothateveryMAPisanMEP,butnotviceversa,seealso[7].Weassumetheprocesstobecovariancestationary,sothatisthestationaryvectorfortheprocessatembeddedeventpoints(i.e.,
).Theexpressionforthelag-covariance,the
covariancebetweenthefirstintervalandthe,is
(3)
2
Hence,theauto-correlationatlag-,r[]canbefoundbydividing[]bythevariance
(4)
Finally,themarginalprocessismatrixexponentialwithdensityasgiveninequation(1).
Now,wediscusstheapproachusedtoconstructthearrivalprocessessuchthatwehaveindependentcontroloverthecoefficientofvariation()andcoefficientofcorrelation().When,weusethePoissonprocess
and.Fornon-exponentialwith
renewalprocesses,weuseMarie’sconstruction[11]fordistributions(validfor)whichisderivedbyfittingtheparametersofaCoxiandistributionandwiththirdmomentequalto
(5)
Theprocesswehavejustdescribedleadstouncorre-latedrandomvariables.Inordertoconstructcorrelatedprocessesthatsharethesamemarginals,weusetheapproachpresentedin[12]toconstructprocesseswith
forgeometricallydecayingcovariance.Define
as:
(6)
Theconstructedintroducesgeometricallydecayingcorrelationsintheprocess,whileleavingthemarginalsinvariant:
Weconsiderthethreetypesofarrivalprocesses:(1)Poisson(=1),(2)high,butuncorrelatedand(3)
andcorrelated.Now,wewilldiscusshowtohigh
formanycombinationsofanddecidethevalueof
streamtypes.
Overallmismatchbetweenstreamsandhascon-tributionsfrommismatchintheiraveragerates(),valuesofcoefficientsofvariation()andcorrelation().Hence,wedefinethemismatchbetweenstreamsandas
;
,,):Whenoneofthestreams,
butissay,isnotPoissonandhasahigh
uncorrelatedandissameasthepreviouscase,i.e.
,then,wepresentresultsin
Figure3,whereisderivedfrom8.Forpresented
andforresults,weuse
stream,wehad.
2)
0.950.94P[Queuelength > 0]--->0.930.920.910.90.890.880.87
where,isthecontributionofratestotheoverall
iscon-mismatchbetweenthestreams,andsimilarlytributionofandthatofcoefficientofcorrelation.Wedefine
(8a)
stream pstream q(8b)(8c)
and
0.86
10.5
1111.51212.513
pq
13.51414.515
IncaseboththestreamsarePoisson,,sincenodistortionoccurs.Bothstreamshaveforanyratioofrates.1)Poisson;,,):Whenoneofthestreams,say,isPoisson()andishavinghighandisalsocorrelated(i.e.
),then,wepresentresultsinFig-ure2,whereisdeterminedbasedon(8)and
.
Increasing Λ ----->
Fig.3.
forstreams
and
forincreasing
0.940.930.92P[Queuelength > 0]--->0.910.90.890.880.870.860.850.840.83
5.5
stream pstream q
66.577.58
pq
8.599.510
Increasing Λ ----->
Fig.2.
forstreams
and
forincreasing
Observethatwedoobservedistortions.Since,isminimal(forbothstreams)forlowervaluesof,metric(8)isameaningfulmetrictobeminimizedinordertoensurethatthedistortionsinthestreamsareminimal.Similarpatternswereobservedforothervalues
and.of
Observethat,forthepresentedscenario,thesuggested
measureisadequatelycapturingthetrendofdistor-tioninboththestreams.Therefore,weseeitasagoodmetrictobeminimizedsothatthestreamscarriedbythenetworksufferminimaldistortion.Similarresultswereobtainedforstreamswithdifferentandandstreamwithothervaluesof.3):Inthefinalcase,boththestreamshavehighandarealsocorrelated().InFigure4,wepresentresultsforthe
forbothandstreams.We
choosethestreamwith,and.Thestreamhas.Weseethatforthevaluesunderconsideration,thechosenformofadequatelycapturestheextentofdistortioninthestreamsand.Similarbehaviorswereobservedfordifferentvaluesof,andofthestreamandforstream.
Torecap,wenowhaveametric()whichisreadilyavailableforvariouskindsofstreamsunderconsidera-tiontobemultiplexedandcanbedeterminedwithoutfindingthesolutionofthemultiplexerfirst.However,itperfectlyreflectsthenegativeimpactofsharedstreamsonbehaviorfurtherinthenetwork.So,byminimizingthismetricinthetrafficengineeringprocess,onemin-imizestheoverloadandthesystemtimes.Themetricwasdeterminedbyaccountingforthedelaysobservedinthestreamsofstreamsafterdepartingfromtheserver
4
0.9350.930.925P[Queuelength > 0]--->0.920.9150.910.9050.90.8950.890.885
13
stream pstream q
13.51414.51515.5
pq
1616.51717.518
Increasing Λ ----->
Fig.4.
forstreams
and
forincreasing
(multiplexer)ataqueue.
Wepointouttothereaderthatthisisnottheonlywaytoconstructthedistortionmetric,ratheritisoneoftheways.Moresophisticatedmethodscouldbeusedtodefineanothermetricwhichmoreaccuratelyreflectstheimpactofhighvarianceandlongtermcorrelations.Theseremainforfurtherstudy.However,wewillshowintheremainderofthispaper,thebenefitsofincorporatingthisnotionofdistortionintrafficengineering.Evenotherrequirementscanbeincorporatedbycarefullyadjustingthevaluesof.Inthenextsection,wewillshowhowthevalueofdistortionmetric()canbeincorporatedinthetrafficengineeringformulation,independentoftheapproach/criteriausedtocomputethevalueofthedistortionmetric.
Thefollowingparametersareassumedtobeknown:,,,,,and.Forevery,wealso
,and.Weassumethatbasedontheknow
isprecomputeddiscussionsinsectionII,thevalueof
and.Weassumethatapathforevery
generator(suchasthek-shortestpathalgorithm)isusedtogeneratethepaths,.Letbethenumberofcandidatepathsgeneratedfordemand.Wenow
associatedwiththeintroducethedecisionvariable
,pathofdemand.It’sstream
valueis1ifthetrafficofstreamselectsthepath;otherwise,itsvalueis0.Asdiscussedearlier,duetocapacityrestriction,itisquitepossiblethatademandmaynotberouted(networkdesigneroftenavoidsuchsituationsbyover-engineering;fromatrafficengineeringmodelingstandpoint,itisnecessarytoincorporatesuchasituation).Toconsiderthisaspect,weintroducethefollowingconstraints
(9)(10)
Toaddresstheflowofastreamofademandoneachlink(foreachpath),wenowintroducetheindicatornotationtomapbetweenthedemandandthelink,astheyrelatetopathsasfollows:
ifpathofdemanduseslinkotherwise.
III.TRAFFICENGINEERINGFORMULATIONWeconsideranaggregated-flowbasednetwork,wheredataarrivingtoasourceforaspecificdestinationneedstobesentoveroneoftheactiveLSPsbetweenthesourceandthedestination.EachsourcedestinationpairmaintainsitsownsetofLSPs.ThetotalLSPschosentobeactivatedacrossthenetworkaresuchthatthetotalnumberofLSPsflowingthrougheachlinkarerestricted.Wefirstpresentthenotations:
Thebandwidthneededonanylink(denotedby)tocarryflowfordifferentdemandscannowbecapturedbytheamount
Foreaseofrepresentation,weusetomean,,.Sinceeachlinkhascapacity,wehavethefollowingconstraintsforeachlink:
:
:::::::::SetofNodesintheNetwork
SetofdemandpairsgeneratingtrafficinthenetworkSetofstreamsfordemandpairSetoflinksinthenetworkUnitrevenuefromtraffic
Arrivalrate(inMbps)ofthestream,ofthestreamandofthestreamand
MaximumnumberoftunnelsallowedonlinkCapacityoflink(inMbps)
(11)
Next,welimitthenumberofactiveLSPsonanylink
tobelessthan.Furthermore,weneedtointroduceavariablethatcapturesifanygivenpathisbeingusedornot.Thevaluetakenbysuchavariabledependsonthevaluetakenbythecorrespondingflowvariables.Hence,
astunnelactivityvariable,whichis1wedefine
ifanyofthestreamsusethepathand0otherwise.
5
Suchafunctionalitycanbeachievedbyincorporatingthefollowingconstraint:
(16d)(16e)(16f)
(12)
Theconstraintincorporatesandforcesthedependencybetweenandvariables.Whenis0,constraint(12)forcestobe0forall,whenis1,couldbe0or1.Havingobtainedavariablewhichcapturesthetunnelactivity,wearereadytoformulatethetunnelconstraintby
(13)
IV.SOLUTIONAPPROACH
Problem(P)isadiscretequadraticoptimizationprob-lemwhichcanbesolved,forexample,usingapproachespresentedin[14],[8].Althoughtheseapproachesareuseful,webaseoursolutionapproachonthespecialstructureoftheobjectivefunctionandtheconstraintswhichsimplifiesthesolutionapproach.Suchasimplifi-cationisachievedbydecouplingtheobjectivefunctionandconstructingtheformulations(P)and(P)(pre-sentedinthefollowingsubsection).
(14)
Thegoaloftrafficengineeringistomaximizerevenuebyflowingthedemandundervariousconstraintswhileminimizingtheoverallmismatchduetotrafficstreamssharingtunnelsinthenetwork.Thefirstcomponentwhichmaximizesthetotalweightedflowacceptedbythenetworkcanbeexpressedas
A.DecouplingPhase
Observethattheobjectivefunctionofproblem(P)hastwocomponents.Firstcomponentneedstobemaximized(totalcarriedflow)andisintegerlinearinnature.Thesecondcomponentneedstobeminimized(themismatchbetweenthestreamssharingaLSP)andisquadraticintegerinnature.Hence,wesplittheobjectivefunctionintotwopartsanduseatwo-tierapproachsimilartotheonepresentedin[13].Problem(P)maximizesthefunction
f(17)
Nowweformthesecondcomponentwhichminimizes
themismatchbetweenthestreams.Noticethatween-counterdistortionsonlywhenfordemandtherearetwostreamsandwhichsharethesamepath.Inotherwords,onlywhen,wehavea
).Summingitacrossallthecostduetomismatch(
demandsandallthestreams,weget
where.Wenowassimilatealltheprevi-ouslydiscussedobjectivesandconstraintstopresentthecompleteformulationofProblem(P)as:
f
(15)
Thisobjectivefunctionisconstrainedbythesetofequations(16).Thisobjectivefunctionmaximizesthetotalweightedcarriedflowbythenetwork.Letthesolutionoftheproblembef.
Next,weminimizethesecondordermismatchbe-tweentheflowssharingatunnelwhilekeepingtheweightedcarriedflowatitsminimalvalue.Wecanalsosetasideapriceintermsofcompromiseincarriedweightedflow()willingtobeacceptedinordertominimizethesecondordermismatchbetweenthestreamssharingatunnel.ThefunctiontobeminimizedbyProblem(P)willbe
Subjectto:
f
(18)
(16a)
(16b)(16c)
6
Thisobjectivefunctionisrestrictedbyconstraint
(19)
alongwiththesetofconstraints(16).
NotethatFormulation(P)isaquadraticintegerprogrammingproblem.Theadditionalconstraint(19)ensuresthatthevalueofvariablesxareonlyadjustedinsuchawaythattheweightedacceptedflowdoesnotdecreasefrombymorethan.Theproblemonlymovesthevariablesxandwaroundinsuchawaythatweightedacceptedflowstillremainsinthevicinityoftheoptimalsolution.
Thecostfunction(18),modeledasaquadraticintegerfunctionmakestheabovepresentedformulationhardtosolve.Notehowever,theproductofandtakesonlytwopossiblevalues,makingitpossibletocapturethesamebehaviorusingalinearfunctionbyusingoneextravariable(),Thisapproachbuildsuponthespecialstructureoftheproblem;itnotonlyavoidsthenon-linearitybutalsotheaddedvariableisfoundtobecontinuous.Notethatifweintroducetheconstraint
foreveryproducttermandminimizethesumof,thenthenon-linearitycanbesuccessfullyavoided.InTableI,weshowthetranslationbetweenthenon-lineartermandtheconstraintonthevalueofandtheeventualvalueofvariableduetominimizingnatureoftheproblem.Weusetheabove
TABLEI
Cons.on
(value)
where,
subjectto(16b),(16c),(21a),(19),(16e)and(21b),and
subjectto(16d)and(16f).HenceinordertosolveProblem(P),weusethefollowingalgorithm.
AlgorithmicSteps
Thealgorithmrequiressolvingthreesmallerproblemsnamely,,and.Inthefollowingsubsections,wepresentourapproachforsolvingthesethreeseparateproblems.
Solving
ProblemisaspecialcaseofMultipleKnapsackProblem(MKP).MKPisknowntobeNPcomplete.Thus,solvingtheGeneralMKPproblembydirectmeth-odsimposesasevereconstraintonthescalabilityofthesolutionapproach.Inourcase,thevolumeofeachitemisequaltoorinalltheknapsacksandsizeofeachknapsackisintegral,makingthisspecialcaseeffectivelysolvablebyfasterapproaches.BelowweshallshowthattherealwaysexistsanintegralsolutionfortheLPversionofMKP.Moreover,atleastonefeasibleoptimum
solutionoftherelaxed
isintegralandhencetheuseoftheSimplexalgorithmwillgiveustheintegral
solutions.
(RelaxedMKP)canbewrittenas:
subjectto
whereAisathe
xmatrixwithbinaryentries(is
resourcescolumnrequiredofAbycapturingobjectthe’s,theamountofinsack),wisan-vectorofvariables(,),banonnegativeintegercomponents.
,...,
-vectorwithTheorem1:RelaxedMultipleKnapsackProblem(RMKP)withandintegerhasatleastonebinarysolutioninthesetofalloptimalsolutions.
Proof:See[16]forproof.
setset
whichistherelaxedversionofproblemwiththegivenvalueof,membersofthesetascontinuous
asfixedtothealreadyvariablesandelementsof
decidedvalues.
done0change1
whiledone=0ANDchange=1do
solve
isinfeasible
(itreturnsNULL),thenweincreasethevalueofbymultiplyingitwithandsolvetheproblemagain.We
tillwegetasolutionofgoonincreasingthevalueof
if
then
else
doneendifendwhileendif
1
.Werepeattheproceduretill
wefindvariablesoftypes(a)and(b)i.e.problemsizereductionisachieved.
Notethatitispossiblethatwhenthevalueof
oftype(a)aresetto1,andtheproblemisrerun,thesolutionmightbeinfeasiblebecausethecapacityconstraint(16c)isgettingviolated(duetoincreaseofthevalueofto1.0).Forsuchascenario,increasingthevalueofwillnotmaketheproblemfeasible.Toavoidsuchapitfall,wekeeptrackofcurrentstateofallocationonlinkcapacitiesandtunnels(theresources).Whiledecidingthevalueofoftype(a),weincreasethevalueonlyifnoneofthelinksaregettingviolated,andaccordinglyupdatethesetsand.Otherwise,wedonotupdatethesetsandletstillbeavariable.Suchacomplicationdoesnotarisewhendecidingfortypes(b)and(c).
Finally,whenweareunabletogetanymorereductioninthesizeoftheproblem,wesolvetheMIPproblemusingdirectbranch-and-boundmethods.Duringexperi-mentsitwasobservedthatthesizeofsuchareducedproblemisfairlysmallandhencedoesnotprovetobealimitation.Hence,wehaveafeasiblesolutionwithall
.
Solving
,9
Observethattheproblemisanunconstrainedoptimizationproblemwithvariableu.Thefunctiontobe
minimizedisnonsmooth,weusesub-gradientapproachtosolvethedualproblem.Thismethoditeratesonthedualvariableu.Thusgiventhevalueofu,once
andarethesolutionstothesubproblems
,forisobtained,adualsubgradient,
computedusing
24
16
35
(28)(29)
Fig.5.SampleNetwork
Thenthedualmultiplier
isupdatedusing
max
wherethestepsizes,
,isgivenby
forachosenvalueof.
Regardingthegenerationofafeasiblesolution,itisknownthatthefinalsolutionderivedfromthealgorithmpresentedabovemightnotbefeasible(someoftheconstraintsmightbeviolated).Hencefeasiblesolutionneedstobederivedfromthegivenvaluesofxandw.Wetakethevaluesofwasgivenandadjustthevaluesofxsoastomakethesolutionfeasibleandrecomputethevalueofobjectivefunction.Westorethevaluesofxandwcorrespondingtothemaximumencounteredduringalltheiterations.
V.RESULTS
AND
DISCUSSION
Inthissection,westudythebehaviorofformulation(P)andsubsequentallocationofstreamsundervariousscenarios.Wehaveimplementedoursolutionmethodin
usingCPLEXlibrariestosolvethesubproblems.
Weevaluatetheperformanceoftheformulation(P)viz-a-vizanaiveformulation(P)whichwasintroducedinsubsectionIV-A.Observethattheformulation(P)doesnotaccountforsecondordercharacteristicsofthestreamsandonlyensuresthattheallocationisrestrictedbythecapacityandthenumberoftunnels.WesolvetheformulationusingasimilarsuccessiveapproximationtechniqueasthatpresentedinAlgorithm1.Theobtained
solutionisthenevaluatedforpresenceofcorrelationsjustasthe(P)solutioni.e.,basedonthemetric.
WepresentresultsforastudyconductedonthesamplenetworkgiveninFigure5.Whilewehaveconductedourstudyforotherexamplenetworks,wewilllimitourdiscussiontojustthissamplenetworkduetolackofspace.Here,weassumedthatthelinksofthesamplenetworkhaveacapacityofMbps,referredtoasbaselinecapacity.Fortheseexperiments,weonlyassumeonedemandbetweennode1andnode6andgenerate8pathsbetweenthetwonodes.Weassumethatthedemandhas20sourcestoroute.Thesesourcesarevariedinnatureintermsoffirstandsecondordercharacteristics.Foursourceswithaveragerate10,15,20and25havewithnocorrelation.Foursourceswithaveragerates10,15,20and25haveand
.Otherfoursourceshaveaveragerates10,15,
20and25havewith.Foursourceswithaveragerates10,15,20and25haveand
.Finally,foursourceswithaveragerates10,15,
20and25haveand.Wecomparethevolumeofacceptedflows()andthecorrelationcost()inthefinalsolutionofformulations(P)and(P)inthefollowingexperimentalscenariosforthesamplenetwork.
Inthefirstscenario,allthelinkshavebaselinecapacityandthenumberofallowedtunnelsare3foreachlink.WepresentresultsinFigure6.Observethatbasedonthechosencapacityandtunnels,thenetworkisunder-provisionedandhenceinthefinalsolution,allthetrafficstreamsarenotaccepted.Bothformulations(P)and(P),onlyactivatetwotunnels(duetotunnelingconstraint)andhadtoroutetheacceptedsourcesonthemonly.Althoughboththeformulationschoosesamevolumeofflowonboththetunnels(about100Mbpseach),formulation(P)choosessourceswhileaccountingfortheirsecondordercharacteristicsalsoandachievessignificantreduction(about75%)inthetotalcorrelationcost().
10
120 100----- f1 ----> 80 60 40 20 0 0
(P)(P1)
----- f2 ----> 1 2 3 4 5 6 7
450 400 350 300 250 200 150 100 50 0
(P)(P1)
----- f1 ----> 50 40 30 20 10
(P)(P1)
----- f2 ----> 0 1 2 3 4 5 6 7
0
0 1 2 3 4 5 6 7
90 80 70 60 50 40 30 20 10 0
(P)(P1)
0 1 2 3 4 5 6 7
# of paths for the demand pair ---------># of paths for the demand pair ---------># of paths for the demand pair ---------># of paths for the demand pair --------->
Fig.6.
and
with
and100%capacity
160 140 120----- f1 ----> 100 80 60 40 20
0
1 2
3 4 5 6 7 0 0
Fig.7.
and
with
and100%capacity
200 150 100 50 0
(P)(P1)
----- f2 ----> 1600 1400 1200 1000 800 600 400 200 0
(P)(P1)(P)(P1)
----- f2 ----> 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7
900 800 700 600 500 400 300 200 100 0
(P)(P1)
----- f1 ----> 0 1 2 3 4 5 6 7
# of paths for the demand pair ---------># of paths for the demand pair ---------># of paths for the demand pair ---------># of paths for the demand pair --------->
Fig.8.
and
with
and300%capacityFig.9.
and
with
and300%capacity
Inthenextscenario,weincreasethenumberofacceptabletunnelsto7.Observethatthenetworkisover-provisionedintermsoftunnelswhereasstillconstrainedinavailablecapacityonlinks.InFigure7,wepresenttheresults.Duetocapacityrestrictions,boththeformu-lationscouldnotacceptallthesources.However,sincemoretunnelsareavailable,correlationcostforboththeformulationshasdecreased.Interestingly,formulation(P)activatesonly4tunnelswhile(P)chooses5tunnels.But,sincetheapproachusedby(P)todistributethetrafficstreamsoverthesetunnelsonlyaccountedforca-pacityconstraint,itaccumulated600%morecorrelationcostascomparedtoformulation(P).
Next,weincreasethecapacityoflinksto300%ofthebaselinecapacityandrestricttheallowednumberoftunnelsto3.Observethatthenetworkisover-provisionedincapacitybutconstrainedinnumberoftun-nels.WepresentresultsinFigure8.Duetoavailabilityofcapacity,formulation(P)activatesonly2tunnelsandmultiplexesallthesourcesontothese2tunnels,whereasformulation(P)activates5tunnelsanddistributesthesourcesonallthefivetunnels.Boththeformulationsacceptallthesourcesandleadtoextensivemultiplexingoftrafficstreams,resultinginhighcorrelationcost.Forthisscenario,formulation(P)doesnotgivesignificantreductionincorrelationcostoverformulation(P)(stillhas10%decrease).
Next,weincreasethecapacityoflinksto300%ofbaselinecapacityandthenumberofacceptabletunnelsto7.Notethatthenetworkisover-provisionedinbothcapacityandthenumberofavailabletunnels.WepresentresultsinFigure9.Observethatformulation(P)activates
7(oftotal8)tunnels,whereasformulation(P)selectsonly5tunnels.Since,formulation(P)hasnoknowledgeofcorrelationcost,itwouldnotinitiateanewtunnelalthoughtheintermediaryrouterscaneasilysupportit.Itwillrathermultiplexthesourcesintothesametunnelsaslongasitdoesnotviolatethecapacityconstraint.However,formulation(P)spreadsallthesourcesoverthemaximumavailabletunnelsleadingtoflowallocationwith70%lesscorrelationcost.
Fortheaboveconsideredscenarios,wepresentthetotalacceptedflowandtotalaccumulateddistortionfortheoveralldemandpairinTableII.Inthefirstcolumn,wehavethecapacityoflinkswithreferencetobaselinecapacity(100%and300%).Inthesecondandthirdmeta-column,wehaveequalto3and7,respectively.Foreachcombinationoftunnelsandcapacity,wepresentthevaluesofacceptedflowvolume()andaccumulatedcorrelationcost()fortheformulations(P)and(P).Observethattheformulation(P)alwaysensuresabetter
TABLEII
TOTAL
AND
FORTHEFOURSCENARIOS
(P)
(P)
200
300%
1505
195
1660
185
800
185
1145
flowallocationthanthatofthenaiveallocationstrategyof(P).Thevalueoftotalcorrelationisdrasticallyreducedwhileacceptingoverallsamevolumeofflows.However,theextentofimprovementachieveddepends
11
uponthestateofthenetworkintermsofprovisioningofcapacityandtunnels.Thereductioninthecostofcor-relationrangesfrom80%to10%whilemaintainingthesametotalvolumeofacceptedflows.Wealsoobservedsimilarresultsforothernetworks.
Insummary,theaboveresultsshowthatindeedtheformulationispowerfulandthatitcapturesthebasicmotiveofminimizingdistortioninthepresenceoftun-nelingandcapacityconstraints.Moreso,itadequatelyrespondstovariouspossiblescenariosoftunnelandcapacityrestrictions.
VI.CONCLUSION
Wepresentanapproachtowardseffectivetrafficen-gineeringofabackbonenetworkwithheterogeneoussourcesandtunnelingconstrainttoaddressfortrafficdistortion.Weevaluatethetrade-offbetweendistortionssufferedbyindividualstreamsandtherequirednumberoftunnelsforeachlink.Towardsthisend,wefirstconstructametric()whichcapturesthedistortionsencounteredwhentwostreamsshareatunnel.Usingthemetric,weformulatetheproblemofdeterminingtheroutingofstreamssuchthatthedistortioninindi-vidualstreamsareminimal.Theproblemissolvedbydecouplingtheproblemintotwophases.Thefirstphasesolutionformsaconstraintinthesecondphase.ThesecondphaseissolvedusingLagrangiandecomposition.Wepresenttheresultsforasamplenetwork.Theresultsshowthattheformulationisinfactpowerfulandthatthesolutionminimizesthedistortionswhilehonoringthetunnelingconstraint.Thesolutionalsoprovidestheroutingofsourcesandthecapacityrequirementoftheallocatedtunnels.
REFERENCES
[1]N.Akar,N.C.OguzandK.Sohraby,Anoverviewof
TELPACK,IEEECommunicationsMagazine,vol.36,No.8,pp.84–87,1998.
[2]A.LaCorte,A.Lombardo,G.Schembra,Modelingsu-perpositionofON-OFFcorrelatedtrafficsourcesinmul-timediaapplications,IEEEINFOCOM,pp.993-1000,1995.
[3]Q.He,M.Ammar,G.Riley,H.Raj,R.Fujimoto,Map-pingPeerBehaviortoPacket-LevelDetails:AFrameworkforPacket-LevelSimulationofPeer-to-PeerSystems,proceedingsofIEEE/ACMMASCOTS,pages71-78,October2003.
[4]A.Heindl,K.Mitchell,A.vandeLiefvoort,Thecor-relationregionofsecondorderMapswithapplicationstoQueueingNetworkDecomposition,proceedingsofTOOLS(LNCS2794),pp.237-254,IL,2003.
[5]M.Held,P.WolfeandH.Crowder,ValidationofSub-GradientOptimizationMathematicalProgramming,Vol6,pp62-88,1974.
[6]D.P.Heyman,T.V.Lakshman,andA.Tabaabal,Sta-tisticalanalysisofMPEG2-codedVBRvideotraffic,inProc.SixthInt.WorkshopPacketVideo,Sept.1994.[7]Y.Lee,A.vandeLiefvoort,V.Wallace,Modelingcor-relatedtrafficwithgeneralizedIPP,PerformanceEvalu-ation,pages99-114,40(2000).
[8]Y.Li,P.M.Pardalos,K.G.Ramakrishnan,M.G.C.
Resende,LowerBoundsfortheQuadraticAssignmentProblem,AnnalsofOperationsResearch,50(1994),pp.387-411.
[9]L.Lipsky,Queueingtheory:Alinearalgebraicapproach
MacMillan,NewYork,1992.
[10]L.Lipsky,P.Fiorini,W.Hsin,A.vandeLiefvoort,
Auto-correlationoflag-kforcustomersdepartingfromsemi-MarkovProcesses,TechnicalReport,TUM-,
TechnicalUniversityMunich,1995.[11]R.Marie,M´ethodesiterativesderesolutiondemod´eles
mathematiquesdesyst´emesinformatiques,R.A.I.R.O.Informatique/Comput.Sci.,12,(1978),107-122.
[12]K.Mitchell,ConstructingCorrelatedSequenceofMa-trixExponentialswithInvariantFirst-OrderProperties,OperationsResearchLetters,vol.28,pages27-34,2001.[13]D.MitraandK.G.RamakrishnanTechniquesforTraffic
EngineeringofMultiservice,MultipriorityNetworks,BellLabsTech.JournalVol.6,No.1,pp139-151,Jan2001.[14]P.M.Pardalos,Y.Ye,C-G.Han,Algorithmsforthe
solutionofquadraticknapsackproblems,LinearAlgebraanditsApplications,152(July,1991),pp.69-91.
[15]S.L.ScottandP.Smyth,TheMarkovModulatedPoisson
ProcessandMarkovPoissonCascadewithApplicationstoWebTrafficData,inBayesianStatistics7,OxfordUniversityPress,pp.671-680.
[16]S.Srivastava,B.Krithikaivasan,D.Medhi,M.Pioro,
TrafficEngineeringinthepresenceofTunnelingandDiversityConstraints:FormulationandLagrangianDe-compositionApproach,proceedingsof18InternationalTeletrafficCongress,pages461-470,Berlin,2003.
[17]S.Srivastava,K.Mitchell,A.Liefvoort,Correlations
InducedinaPacketStreambyBackgroundtrafficinaMultiplexedEnvironment,proceedingsof18Interna-tionalTeletrafficCongress,pages511-520,Berlin,2003.[18]S.R.Thirumalsetty,D.Medhi,TrafficEngineeringfor
SurvivableBook-AheadGuaranteedServices,TechnicalReport,SICE,UniversityofMissouri-KansasCity,MO.
12
因篇幅问题不能全部显示，请点此查看更多更全内容