Performance Evaluation of Complex Systems

Thefastevolutionandtheincreasedpervasivenessofcomputersandcom- nicationnetworkshaveledtothedevelopmentofalargevarietyofcomplex applicationsandserviceswhichhavebecomeanintegralpartofourdailylives. Modernsocietywidelyreliesoninformationtechnologies. Hence,theQuality ofService,thatis,thee?ciency,availability,reliability,andsecurityofthese technologies,isanessentialrequirementfortheproperfunctioningofmodern society. Inthisscenario,performanceevaluationplaysacentralrole. Performance evaluationhastoassessandpredicttheperformanceofhardwareandsoftware systems,andtoidentifyandpreventtheircurrentandfutureperformancebo- lenecks. Inthepastthirtyyears,manyperformanceevaluationtechniquesandtools havebeendevelopedandsuccessfullyappliedinstudiesdealingwiththec- ?gurationandcapacityplanningofexistingsystemsandwiththedesignand developmentofnewsystems. Recently,performanceevaluationtechniqueshave evolvedtocopewiththeincreasedcomplexityofthecurrentsystemsandtheir workloads. Manyoftheclassicaltechniqueshavebeenrevisitedinlightofthe recenttechnologicaladvances,andnoveltechniques,methods,andtoolshave beendeveloped. Thisbookisorganizedaroundasetofsurveypaperswhichprovideac- prehensiveoverviewofthetheories,techniques,andtoolsforperformanceand reliabilityevaluationofcurrentandnewemergingtechnologies. Thepapers,by leadinginternationalexpertsinthe?eldofperformanceevaluation,arebasedon thetutorialspresentedattheIFIPWG7. 3InternationalSymposiumonCom- terModeling,Measurement,andEvaluation(Performance2002)heldinRome onSeptember23-27,2002. Thepapersaddressthestateoftheartofthetheoreticalandmethodological advancesintheareaofperformanceandreliabilityevaluationaswellasnew perspectivesinthemajorapplicationdomains. Abroadspectrumoftopicsis coveredinthisbook. Modelingandveri?cationformalisms,solutionmethods, workloadcharacterization,andbenchmarkingareaddressedfromametho- logicalpointofview. Applicationsofperformanceandreliabilitytechniquesto variousdomains,suchas,hardwareandsoftwarearchitectures,wiredand- relessnetworks,Gridenvironments,Webservices,real-timevoiceandvideo applications,arealsoexamined. Thisbookisintendedtoserveasareferenceforstudents,scientists,and- gineersworkingintheareasofperformanceandreliabilityevaluation,hardware andsoftwaredesign,andcapacityplanning. VI Preface Finally,aseditorsofthebook,wewouldliketothankallauthorsfortheir valuablecontributionsandtheire?ortandcooperationinthepreparationof theirmanuscripts. July2002 MariaCarlaCalzarossa SalvatoreTucci TableofContents G-Networks:MultipleClassesofPositiveCustomers,Signals,and ProductFormResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 ErolGelenbe SpectralExpansionSolutionsforMarkov-ModulatedQueues . . . . . . . . . . . . 17 IsiMitrani M/G/1-TypeMarkovProcesses:ATutorial . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 AlmaRiska,EvgeniaSmirni AnAlgorithmicApproachtoStochasticBounds . . . . . . . . . . . . . . . . . . . . . . . 64 J. M. Fourneau,N. Pekergin DynamicSchedulingviaPolymatroidOptimization. . . . . . . . . . . . . . . . . . . . . 89 DavidD. Yao WorkloadModelingforPerformanceEvaluation. . . . . . . . . . . . . . . . . . . . . . . . 114 DrorG. Feitelson CapacityPlanningforWebServices(TechniquesandMethodology) . . . . . . 142 VirgilioA. F. Almeida End-to-EndPerformanceofWebServices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 PaoloCremonesi,GiuseppeSerazzi Benchmarking. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .