Necessary and sufficient conditions for representing

generaldistributionsbyCoxians

TakayukiOsogami

MorHarchol-Balter

February24,2003

CMU-CS-02-178

SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213

Abstract

AcommonanalyticaltechniqueinvolvesusingaCoxiandistributiontomodelageneraldistribution,wheretheCoxiandistributionagreeswithonthefirstthreemoments.ThistechniqueismotivatedbytheanalyticaltracabilityoftheCoxiandistribution.AlgorithmsformappinganinputdistributiontoaCoxiandistributionlargelyhingeonknowingapriorithenecessaryandsufficientnumberofstagesintherepresentativeCoxiandistribution.Inthispaper,weformallycharacterizethesetofdistributionswhicharewell-representedbyan-stageCoxiandistribution,inthesensethattheCoxiandistributionmatchesthefirstthreemomentsof.Wealsodiscussafewcommon,practicalexamples.Lastly,wederiveapartialcharacterizationofthesetofbusyperioddurationswhicharewell-representedbyan-stageCoxiandistribution.

CarnegieMellonUniversity,ComputerScienceDepartment.Email:osogami@cs.cmu.edu

CarnegieMellonUniversity,ComputerScienceDepartment.Email:harchol@cs.cmu.edu.ThisworkwassupportedbyNSFCareerGrantCCR-0133077,byNSFITRGrant99-167ANI-0081396andbySpinnakerNetworksviaPittsburghDigitalGreenhouseGrant01-1.

Keywords:momentmatching,Coxiandistribution,busyperiod,phase-typedistribution,normalizedmoment,queueing,matrixanalytic

1Introduction

Background

Approximatinggeneraldistributionsbyphase-type(PH)distributionshassignificantapplicationintheanalysisofstochasticprocesses.Manyfundamentalproblemsinqueueingtheoryarehardtosolvewhengeneraldistributionsareallowedasinputs.Forexample,thewaitingtimeforanM/G/cqueuehasnoniceclosedformulawhen

,whilethewaitingtimeforanM/M/cqueueistriviallysolved.Tractability

istoapproximate

byaPH

ofM/M/cqueuesisattributedtothememorylesspropertyoftheexponentialdistribution.Apopularapproachtoanalyzingqueueingsystemsinvolvingageneraldistribution

distribution.APHdistributionisaverygeneralmixtureofexponentialdistributions,asshowninFigure1[19].TheMarkoviannatureofthePHdistributionfrequentlyallowsaMarkovchainrepresentationofthequeueingsystem.OncethesystemisrepresentedbyaMarkovchain,thischaincanoftenbesolvedbymatrix-analyticmethods[20,16],orothermeans.

Whenfittingageneraldistribution

toaPHdistribution,itiscommontolookforaPHdistribution

whichmatchesthefirstthreemomentsofDefinition1Adistributionmoments.

.Inthispaper,wesaythat:

iswell-representedbyadistributionif

and

agreeontheirfirstthree

Ithasbeenshownthatmatchingthreemomentsissufficientforaccuratemodelingofmanycomputersystems[9,23].Matchingfewermomentsislessdesirablesincesomequeueingsystems,e.g.thequeue,haveresponsetimeswhichareheavilydependentonthethirdmomentof

Mostexistingalgorithmsforfittingageneraldistribution

[31,11].

toaPHdistribution,restricttheirattention

toasubsetofPHdistributions,sincegeneralPHdistributionshavesomanyparametersthatitisdifficulttofindtime-efficientalgorithmsforfittingtothem[30,13,12,26,18].ThemostcommonlychosensubsetistheclassofCoxiandistributions,showninFigure2.CoxiandistributionshavetheadvantageofbeingmuchsimplerthangeneralPHdistributions,whileincludingalargesubsetofPHdistributionswithoutneedingadditionalstages.Forexample,foranyacyclicPHdistributiondistribution

,thereexistsaCoxian

withthesamenumberofstagessuchthat

and

havethesamedistributionfunction

[5].InthispaperwewillrestrictourattentiontoCoxiandistributions.MotivationandGoal

WhenfindingaCoxiandistribution

whichwell-representsagivendistribution

,itisdesirablethat

beminimal,i.e.,thenumberofstagesinbeassmallaspossible.Thisisimportantbecauseitminimizes

theadditionalstatesnecessaryintheresultingMarkovchainforthequeueingsystem.Unfortunately,itis

1

p00p04p03p02p01Expp14p13p12p21µ1Expp24p23p32Expµ2µ3p34p43Expµ4p40p30p31p41p42p20p10Figure1:A4-stagePHdistribution.Therearestates,wherethethstatehasexponentially-distributedservicetimewithrate.Withprobabilitywestartinthethstate,andthenextstateis

thatitwillbethelaststate.Thevalueofthestatewithprobability.Eachstatehasprobability

distributionisthesumofthetimesspentineachofthestates.

p11−p1µ1p21−p2µ2p31−p3pnµnFigure2:An-stageCoxiandistribution.Observetherecursivedefinition:withprobabilityvalueiszero,andwithprobability,thevalueisanexponentialrandomvariablewithratebyan-stageCoxiandistribution.

,the

followed

notknownwhatistheminimalnumberofphasesnecessarytorepresentagivendistributiondesignoffittingalgorithmsopen-ended.

byaCoxian

distribution.Thismakesitdifficulttoevaluatetheeffectivenessofdifferentalgorithmsandalsomakesthe

Theprimarygoalofthispaperistocharacterizethesetofdistributionswhicharewell-representedbyan-stageCoxiandistribution,foreach

.

Definition2Let

denotethesetofdistributionsthatarewell-representedbyan-stageCoxiandis-tributionforpositiveinteger.Ourcharacterizationof

willallowonetodetermine,foranydistribution

,theminimal

numberofstagesthatareneededtowell-representbyaCoxiandistribution.Suchacharacterization

willbeausefulguidelinefordesigningalgorithmswhichfitgeneraldistributionstoCoxiandistributions.Anotherapplicationofthischaracterizationisthatsomeexistingfittingalgorithms,suchasJohnsonandTaaffe’snonlinearprogrammingapproach[13],requireknowingthenumberofstages

intheminimal

,whichisnotpositiveforallpossiblechoicesof

.

2

Coxiandistribution.Thecurrentapproachinvolvessimplyiteratingoverallchoicesforourcharacterizationwouldimmediatelyspecify.

[13],whereas

Asecondarygoalofthispaperistospecifythenecessaryandsufficientnumberofstagesneededtowell-representbusyperioddurationsbyCoxiandistributions.FittingbusyperioddurationstoCoxiandis-tributionshasbecomerelevantrecentlyinthesolutionofcommoncomputersystemsproblemsinvolvingcyclestealing,see[9,23].In[9,23],transitionsbetweenstatesinaMarkovchainrepresentbusyperioddurations,whicharemodeledviaCoxiandistributionsfortractability.Inadditiontostandardbusyperiods,itisalsocommontomodelthebusyperiodstartedby

jobs.Thispaperwillspecifythenumberofstages

doesnotalwaysimme-

neededtowell-representsuchbusyperiodsbyCoxiandistributions.

Providingsufficientandnecessaryconditionsforadistributiontobein

diatelygiveoneasenseofwhichdistributionssatisfythoseconditions,orofthemagnitudeofthesetofdistributionswhichsatisfythecondition.Athirdgoalofthispaperistoprovideexamplesofpracticaldistributionswhichareincludedin

forparticularintegers.

Infindingsimplecharacterizationsof,itwillbeveryhelpfultostartbydefininganalternativeto

thestandardmoments,whichwerefertoasnormalizedmoments.Definition3Letsecondmoment

beadistributionandof

bethe-thmomentof

for

.Thenormalized

andthenormalizedthirdmoment

of

aredefinedtobe

Noticethecorrespondencetothesquaredcoefficientofvariability,

,andtheskewnessfactor,:

and

Ourresults

Whilethegoalofthepaperistocharacterizethesetofthekeyideasinthepaperisthatthereisasetthat

,thischaracterizationturnsouttobeugly.One

whichisverycloseto

insize,such

hasaverysimplespecificationvianormalizedmoments.Thus,muchoftheproofsinthispaper

revolvearound.

Definition4Forintegers,let

denotethesetofdistributionswiththefollowingpropertyon

theirnormalizedmoments:

and

:

(1)

Themaincontributionofthispaperisaderivationofthenestedrelationshipbetweenalloffor

and

for

.ThisrelationshipisillustratedinFigure3andproveninSection3.Therearethreepointsto

observe:(i)

isapropersubsetof

forallintegers

,andlikewise

isapropersubset

;(ii)

iscontainedin,where

andcloseto

insize;providingasimplecharacterization

;(iii)

isalmostcontainedin

forallintegers(moreprecisely,wewillshow

isthesetofdistributionswell-representedbyanErlang-ndistribution).

Thisresultyieldsanecessarynumberandasufficientnumberofstagesforagivendistributiontobewell-representedbyaCoxiandistribution.Additionalcontributionsofthepaperaredescribedbelow:

Withrespecttothesettobein

,wederivetheexactnecessaryandsufficientconditionforadistribution

asafunctionofthenormalizedmomentsof

.ThisextendstheresultsofTelekandHeindl,

denotethe

.

whoanalyzed,whichisasubsetof

.(SeeSection2).

WenextinvestigatethefittingofM/G/1busyperiodsbyCoxiandistributions.LetdurationofanM/G/1busyperiodwhere

isanarbitrarydistributionwithfinitethirdmomentandwhere

thesizeofthejobstartingthebusyperiodisin.Weprovethatanysuch

hasdistributionin

Thisissurprisinginthatthenumberofstageswhichsufficetorepresentthebusyperiodisdeterminedsolelybythefirstjobstartingthebusyperiod,whichmaybeasimplesetupcost,anditisnotrequiredtoconsiderthedistributionsoftheotherjobsinthebusyperiod.Furthermore,letanM/G/1busyperiodwhereperiodisstartedby

denotethedurationof

isanarbitrarydistributionwithfinitethirdmomentandwherethebusy

jobswithservicetimedistributionin

where

isthenumberofPoissonarrivals

duringarandomvariablewithdistributionin.Weprovethatanysuchisin

.(SeeSection4).

Lastly,weprovideafewexamplesofcommon,practicaldistributionsincludedintheset

.Alldistributionsweconsiderhavefinitethirdmoment.TheParetodistributionandtheBounded

Paretodistribution(asdefinedin[7])havebeenshowntofitmanyrecentmeasurementofjobservice

4

SvSSS(4)(3)(2)(2)

Sv

(3)(4)

Sv

Figure3:Themaincontributionofthispaper:asimplecharacterizationofby.Solidlinesdelineate(whichisirregular)anddashedlinesdelineate(whichisregular–hasasimplespec-and.isclosetoinsizeandiscontainedinification).Observethenestedstructureof

.isalmostcontainedin.

requirementincomputingsystems,includingHTTPrequests[3,4],UNIXjobs[17,8],andthedurationofFTPtransfers[24].WeshowthattheBoundedParetowithhighvariabilityisinconditionsunderwhichtheParetoanduniformdistributionsarein

.Wealsoprovide

foreach

.(SeeSection5).

2Fullcharacterizationof

TheTelekandHeindl[29]resultmaybeexpressedintermsofnormalizedmomentsasfollows:Theorem1(Telek,Heindl)

iff

isinthefollowingunionofsets:

denotesset

Sinceonlyanoutlineofaproofisgivenin[29],wederiveourownproofofTheorem1in[21]forcompleteness.WenowshowasimplercharacterizationofTheorem2

:

iff

isinthefollowingunionofsets:

.

AsummaryofTheorems1and2isshowninFigure4.Figure4(a)illustrateshowcloseinsize.Figure4(b)showsthedistributionswhicharein

m3and

are

butnot

.

(2)(2)*m3SV3(2)3SSS(2) (2)SV23/22m223/22m2Figure4:(a)Thethicksolidlinesdelineate.Thedashedlines(stripedregion)showAgain,thethicksolidlinesdelineate.Theshadedareashowstheregion.

.(b)

Proof:[Theorem2]Thetheoremwillbeprovedbyreducingsomedistribution

,where

to

andemployingTheorem1.The

proofhingesonthefollowingobservation:Anarbitrarydistribution

iff

iswell-representedby

withprobabilitywithprobability

forsomeLet

.Itthereforesufficestoshowthat

isinset(2).

bethenormalized-thmomentof

bethenormalized-thmomentof

and

for

.

Observethat

for

and

Thus,

isinthefollowingunionofsets:

(3)

Wewanttoshowthat

isinset(2).Todothis,werewriteset(2)as

(4)

Observethat(3)and(4)arenowinsimilarforms.Wenowprovethatset(3)isasubsetofset(4),andset(4)isasubsetofset(3).ThetechnicaldetailsarepostponedtoAppendixB,Lemma9.1.

conditionsonnormalizedmomentsintermsof

denotessetexample,

denotesthesetofdistributionsthatsatisfytheconditionsforsome.For

s.t.and.

7

m33Sv(2)2E3E2Sv(3)Sv(4)3/2E31Sv1(32)14/33/22m2Figure6:Depictionofsetsforasafunctionofthenormalizedmoments.Theoutermostdottedlines(and)delineatethesetofallthepossiblenonnegativedistributions(thatis,anynonnegativedistributionsatisfiesand)[14].foraredelineatedbydashedlines.

Lemma3.1Lemma3.2

.

.

,thelemmafollowsfrom(1),(5),and

Proof:[Lemma3.1]Theproofproceedsbyinduction.WhenTheorem2.Assumethat

for

.Foranydistribution

,thereexists

a-stageCoxiandistribution

bywhich

iswell-represented,wherecanbeexpressedas

andwherethen

isanexponentialdistributionand

isa

-stageCoxiandistribution.Bytheassumption

ofinduction,

.Weprovethat(i)if

,then

and(ii)if

,

.

.Firstobservethat

(i)Suppose

8

whichisminimizedwhen

.Thus,

Next,weprovethat

forall

isindependentof:

Since

at

at

wherethelastinequalityholdsiff

holdsif

9

since

and

and

for

.

(ii)Suppose

inpart(i).Itisalsoeasyto

seethat

,since

isminimizedwhen

and

.Also,since

bypart(i),andhence

.

:Weneedtoshowthat

stageCoxiandistribution.Wewillprovesomethingstronger:that

iswell-representedbysome-iswell-representedbyadistribution

where

,and

isaparticulartwo-stageCoxiandistributionwithnomassprobabilityat

zeroand

isaparticularErlang-(

)distribution.(Fortheintuitionbehindthisparticularwayof

representing,pleasereferto[22]).Thenormalizedmomentsof

arechosenasfollows:

Themeanofmomentsof

ischosenasfollows:

.Itiseasytoseethatthenormalized

andagree:

where

arethenormalizedmomentsof

,and

.Thefirst

condition,

,canbeshownusing

using

:Weagainmustshowthat

iswell-representedbyan

-stageCoxiandistribution.Wewillshowthat

iswell-representedbyadistribution

:

withprobabilitywithprobability

where

themeanofmomentsof

ischosenasfollows:and

.Itiseasytoseethatthenormalized

agree:

11

where

arethenormalizedmomentsof

,and

,since

Since

,

Finally,

.

WewillnowproveTheorem4andLemma4.1.Proof:[Theorem4]Whenassume

,

,andhencethetheoremistrue.Inthefollowingwe

.Let

.Weprovethat

.

Observethattogethertheseimplytheconditionsin(1).Noticethatthefirstthreemomentsof

are

:

and

where

.Thus,

Proof:[Lemma4.1]Let

.

NoticethattheLaplacetransformofis

momentsof

are

13

.Notethat

.Weprovethat

.Thus,thefirstthree

Itiseasytoseethat

and

.Notethat

where

.Thus,

m3PARETO3BPSv(2)2Sv3/2(4)Sv(8)11UNIFORM/TRIANGULAR4/33/22m2Figure7:AsummaryoftheresultsinSection5.Afewparticulardistributionsareshowninrelationto

.BPreferstotheclassofboundedParetodistributionswithhighvariabilitydescribedinDefinition5.Allofthesearecontainedin.UNIFORMreferstotheclassofalluniformdistributionsdescribedinDefinition6.WefindthatthelargertherangeoftheUNIFORMdistribution,thefewerthenumberofstagesthatsuffices.TRIANGULARreferstothesetofsymmetrictriangulardistributions,describedinDefinition7.TheseinterestinglyhavethesamebehaviorastheUNIFORMdistribution.Finally,PARETOreferstotheclassofPareto()distributionswithfinitethirdmoment,describedinDefinition8.Forthisclass,wefindthatthelowerthevalueofthe-parameter,thefewerthenumberofstagesthatareneeded.

workloadsfordistributedserversconsistingofCrayC90andCrayJ90machines[27].Inthissection,weprovethenecessaryandsufficientconditionforaBoundedParetodistributiontobeinusethefollowingdefinition:Definition5

.Formally,we

isasetofBoundedParetodistributionssatisfying

and

inthedefinitionof

theBPdistribution.Theselinesarederivedfrom(7)and(8).Withthisdefinition,thetheoremproveninthissectionisstated:Theorem6

and

,where

15

isthesetofBoundedParetodistributionsnot

in

and

isanemptyset.

Proof:Let

bethenormalized-thmomentofadistribution

for

.When

,the

momentsoftheBoundedParetoare

ByLemmas9.5-9.8inAppendixB,both

and

gotoinfinity.Thus,thereisafinite

such

.

that

and

.Next,considerthecasewith

or

.Byobservingthat

,itiseasytoseethat

goestoinfinityasdoes.Thus,thereisafinitesuchthat

Next,weconsider

andonlyif

.However,since

Thereisafinitesuchthat

for

,too.

intheregion

andzerootherwise.

Definition7

isthedistributionwithdensityfunctionsoftheform

where

and

.

Definition8

isthedistributionwithdensityfunctionsoftheform

.

Withthesedefinitions,thethreedistributionsareformallycharacterizedasfollows:Theorem7Thenormalizedmomentsofsatisfy

all

and

.

Theorem8Thenormalizedmomentsofsatisfy

forall

and

.

17

,where

for

Theorem9Thenormalizedmomentsofdistributionsin

satisfy

whereminimumof

Thus,

,where

,where

,

.andthenormalizedsecondandthirdmomentsof

are

for

,

isanonincreasingfunctionof.So,the

isgivenbyevaluatingitat

andthemaximumisgivenbyevaluatingitat

.

.

arenearlytight.Thisresulthasseveralpracticaluses:First,indesigningalgorithmswhichfitgeneraldistributionstoCoxiandistributions(fittingalgorithms),thegoalistocomeupwithaminimal(fewestnumberofstages)Coxiandistribution.OurcharacterizationallowsalgorithmdesignerstodeterminehowclosetheirCoxiandistributionistotheminimalCoxiandistribution,andprovidesintuitionforcomingupwithimprovedalgorithms.Wehaveourselvesbenefittedfromexactlythispoint:Inacompanionpaper[22],wedevelopanalgorithmforfindingaminimalCoxiandistributionthatwell-representsagivendistribution.Wefindthatthesimplecharacterizationof

providedhereinisveryusefulinthistask.

inthe

Ourresultsarealsousefulasaninputtosomeexistingfittingalgorithms,suchasJohnsonandTaaffe’snonlinearprogrammingapproach[13],whichrequireknowingapriorithenumberofstagesminimalCoxiandistribution.

Inadditiontocharacterizingthosedistributionsinhavedurationsin

,wealsoconsiderwhichM/G/1busyperiods

.Wefindthatthenumberofstageswhichsufficeforabusyperioddurationtobe

well-representedbyaCoxiandistributionis,surprisingly,determinedsolelybythedistributionofthefirstjobinthebusyperiod.Furthermoreweclassifyafewexamplesofcommonandpracticaldistributionsasbeingsubsetsof

forsome.

Futureworkincludesasimplecharacterizationofthesetofdistributionsthatarewell-representedbygeneral-phasePHdistributions.ItisknownthattheErlangdistributionhasthelowestnormalized

secondmomentamongallthe-phasePHdistributions[1].However,alowerboundonthenormalized

thirdmomentof-phasePHdistributionsisnotknown.

References

[1]D.AldousandL.Shepp.TheleastvariablephasetypedistributionisErlang.CommunicationsinStatistics-StochasticModels,3:467–473,1987.

[2]T.Altiok.Onthephase-typeapproximationsofgeneraldistributions.IIETransactions,17:110–116,1985.[3]M.E.CrovellaandA.Bestavros.Self-similarityinWorldWideWebtraffic:Evidenceandpossiblecauses.

IEEE/ACMTransactionsonNetworking,5(6):835–846,December1997.

[4]M.E.Crovella,M.S.Taqqu,andA.Bestavros.Heavy-tailedprobabilitydistributionsintheworldwideweb.

InAPracticalGuideToHeavyTails,chapter1,pages1–23.Chapman&Hall,NewYork,1998.

[5]A.Cumani.Onthecanonicalrepresentationofhomogeneousmarkovprocessesmodellingfailure-timedistri-butions.MicroelectronicsandReliability,22:583–602,1982.

[6]A.FeldmannandW.Whitt.Fittingmixturesofexponentialstolong-taildistributionstoanalyzenetwork

performancemodels.PerformanceEvaluation,32:245–279,1998.

[7]M.Harchol-Balter.Taskassignmentwithunknownduration.JournaloftheACM,49(2),2002.

[8]M.Harchol-BalterandA.Downey.Exploitingprocesslifetimedistributionsfordynamicloadbalancing.In

ProceedingsofSIGMETRICS’96,pages13–24,1996.

[9]M.Harchol-Balter,C.Li,T.Osogami,A.Scheller-Wolf,andM.Squillante.Taskassignmentwithcyclestealing

undercentralqueue.InToappearinProceedingsof23rdInternationalConferenceonDistributedComputingSystems(ICDCS’03).,May2003.Foracopyseehttp://www.cs.cmu.edu/harchol/.

19

[10]G.Irlam.Unixfilesizesurvey-1993.Availableathttp://www.base.com/gordoni/ufs93.html,

September1994.

[11]M.A.JohnsonandM.F.Taaffe.Agraphicalinvestigationoferrorboundsformoment-basedqueueingap-proximations.QueueingSystems,8:295–312,1991.[12]M.A.JohnsonandM.R.Taaffe.Matchingmomentstophasedistributions:Densityfunctionshapes.Commu-nicationsinStatistics—StochasticModels,6:283–306,1990.[13]M.A.JohnsonandM.R.Taaffe.Matchingmomentstophasedistributions:Nonlinearprogrammingap-proaches.CommunicationsinStatistics—StochasticModels,6:259–281,1990.[14]S.KarlinandW.Studden.TchebycheffSystems:WithApplicationsinAnalysisandStatistics.JohnWileyand

Sons,1966.

[15]R.E.A.Khayari,R.Sadre,andB.Haverkort.Fittingworld-widewebrequesttraceswiththeEM-algorithm.In

ProceedingsofSPIE:InternetPerformanceandControlofNetworkSystemsII,volume4523,pages211–220,2001.[16]G.LatoucheandV.Ramaswami.IntroductiontoMatrixAnalyticMethodsinStochasticModeling.ASA-SIAM,

Philadelphia,1999.

[17]W.E.LelandandT.J.Ott.Load-balancingheuristicsandprocessbehavior.InProceedingsofPerformance

andACMSigmetrics,pages54–69,1986.

[18]R.Marie.Calculatingequilibriumprobabilitiesforqueues.InProceedingsofPerformance1980,

pages117–125,1980.

[19]M.F.Neuts.Matrix-GeometricSolutionsinStochasticModels.JohnsHopkinsUniversityPress,1981.

[20]M.F.Neuts.Matrix-GeometricSolutionsinStochasticModels:AnAlgorithmicApproach.TheJohnsHopkins

UniversityPress,1981.

[21]T.OsogamiandM.Harchol-Balter.Necessaryandsufficientconditionsforrepresentinggeneraldistributions

byCoxians.TechnicalReportCMU-CS-02-178,SchoolofComputerScience,CarnegieMellonUniversity,2002.[22]T.OsogamiandM.Harchol-Balter.Aclosed-formsolutionformappinggeneraldistributionstominimalPH

distributions.TechnicalReportCMU-CS-03-114,SchoolofComputerScience,CarnegieMellonUniversity,2003.[23]T.Osogami,M.Harchol-Balter,andA.Scheller-Wolf.Analysisofcyclestealingwithswitchingcost.InTo

appearinACMSigmetrics2003ConferenceonMeasurementandModelingofComputerSystems(SIGMET-RICS’03).,June2003.Foracopyseehttp://www.cs.cmu.edu/harchol/.

[24]V.PaxsonandS.Floyd.Wide-aretraffic:Thefailureofpoissonmodeling.IEEE/ACMTransactionson

Networking,pages226–244,June1995.

[25]D.L.PetersonandD.B.Adams.FractalpatternsinDASDI/Otraffic.InCMGProceedings,December1995.[26]C.SauerandK.Chandy.Approximateanalysisofcentralservermodels.IBMJournalofResearchand

Development,19:301–313,1975.

[27]B.SchroederandM.Harchol-Balter.Evaluationoftaskassignmentpoliciesforsupercomputingservers:The

caseforloadunbalancingandfairness.InProceedingsofHPDC2000,pages211–219,2000.

[28]D.StarobinskiandM.Sidi.Modelingandanalysisofpower-taildistributionsviaclassicalteletrafficmethods.

QueueingSystems,36:243–267,2000.[29]M.TelekandA.Heindl.Momentboundsforacyclicdiscreteandcontinuousphasetypedistributionsofsecond

order.InProceedingsofUKPerformanceEvaluationWorkshop,UKPEW2002,2002.[30]W.Whitt.Approximatingapointprocessbyarenewalprocess:Twobasicmethods.OperationsResearch,

30:125–147,1982.[31]W.Whitt.Onapproximationsforqueues,iii:Mixturesofexponentialdistributions.AT&TBellLaboratories

TechnicalJournal,63:163–175,1984.

20

AProofofTheorems8and9

Proof:[Theorem8]Thefirstthreemomentsof

are

.

Since

.Also,itiseasytoseethat

and

Proof:[Theorem9]Thefirstthreemomentsof

Also,itiseasytoseethat

and

satisfy

satisfy

are

.

set(4)istheunionofthefollowingthreesets:

Itsufficestoprovethat(i),(ii)immediatefromdefinition.Toprove(i),weprovethat

.WefirstshowthatConsideradistribution

,and(iii).(ii)and(iii)are

and..Letbetheupperboundof:

Then,

and

arebothcontinuousandincreasingfunctionsof

for

byLemmas

9.2and9.3.When

,therangeof

is

andhence

.When

,therangeof

is

.Thus,

andhence.Therefore,.However,sinceand

,cantakeanyvaluebetweenthelowerandupperbounds.Therefore,

arecontinuousfunctionsof

.

isanincreasingfunctionof

for

.Theinequalityholdswhen

Lemma9.3Let

.Then,

Let

andthesecondinequalityfollowsfrom

.

iff

,where

Noticethat

(9)

Thus,

that

.Thus,itsufficestoprove

for

.

where

Lemma9.5

Notethat

Lemma9.6

Notethat

.

Proof:Notethat

,

,and

24

.

isanincreasingfunctionfor

for

.Let

.Then,

for

,since

,

,

,and

.If

,

isadecreasingfunctionfor

.

Proof:Notethat

for,itiseasytoseethat

for

when

,welet

Then,

for

,since

,

,and

,

isanincreasingfunctionfor

.If

for

when

.Toseethat

,