Challenges in control engineering of computing systems

IBM Research Report

Challenges in Control Engineering of Computing Systems

Joseph L. HellersteinIBM Research Division

Thomas J. Watson Research Center

P.O. Box 704

Yorktown Heights, NY 10598

Research DivisionAlmaden - Austin - Beijing - Haifa - India - T. J. Watson - Tokyo - ZurichLIMITED DISTRIBUTION NOTICE: This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a ResearchReport for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specificrequests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g. , payment of royalties). Copies may be requested from IBM T. J. Watson Research Center , P.O. Box 218, Yorktown Heights, NY 10598 USA (email: reports@us.ibm.com). Some reports are available on the internet at http://domino.watson.ibm.com/library/CyberDig.nsf/home .ChallengesinControlEngineeringofComputingSystems

JosephL.Hellerstein.

siderableAbstract—Overthelastfewyears,therehasbeencon-systems.commonlyOursuccessexperiencewithapplyinghasbeencontrolthattheorytocomputingtranslatingoccurringandconnectedeffectorbetweencontrolproblemsincomputingtherearesystems—several(actuator)serviceunitsoriented(e.g.,theunitsmaximum(e.g.,responsetimes)levelsdisturbancestoenforceusers);optimizingresourceusage;regulatingnumberserviceofsystemssuchserviceaschangeslevelinagreements;workloads.Developingandadaptingtotodatamodelingthataddressthemanagedtheseproblemsinvolveschallengescontrolrelatedwiththatarenoisy,incomplete,elementand(plant);inconsistent;handingdealingsensorcorrespondeffectorssystemstimedelays).

(especiallywellthattothehavecomplexeffectsthatoftendonotfilters,controltheobjectives;choiceofmeasuredanddesigningoutputs,controlandI.INTRODUCTION

andTherelentlessdeclineinthepriceoftechnologysoftwarehasledtothewidespreadcomputeruseofinformationhardwarescaleitimperativeofcomputing(IT).Asaresult,thedependenceonandthetohavesystemsstablehaswell-behavedgrowndramatically,systems.

makingusedDespitecomputinginpracticethisimperative,whendevelopingformalcontrolnewmethodsarerarelysystemalmostidentificationsystems.Forexample,itisuncommoncapabilitiestofordodisturbances.

unheardoftoofanalyzethecomponentstheresponsetobeofcontrolledthesystemandtoalongOverthelastthreeyears,mycolleaguesandIatIBMsuccesswithresearcherselsewherehavehadconsiderablecontrol)withsystems.toanalyzeusingclassicalanddesigncontrolclosedtheory(mostlydigitalmoreThisworkhasresultedinIBMloopsproductsincomputingthaterablerobustlowerimprovementstodisturbancesinand,insomecases,consid-aredevelopersresponsewithtimes).newinsightsFurther,theirintoourperformancedesignworkhaschoices.

providedaswell(e.g.,IBMhasBasedonourexperience,wecomputinganimportantroletoplayinbelievethethatcontroltheoryThiscontroltutorialsystems,describesespeciallydevelopmentofnewmanycomplexsoftwaresystems.antheorytocomputingofsystems.thechallengesSectionwithIIapplyingprovidesdescribesoverviewSectionvariousofenterprisecontrolproblemscomputinginsystems.SectionIIIloopIVdetailschallengesinthedevelopmentcomputingofsystems.closedsurveysystemsSectionofVI.

relatedforcomputingwork.Oursystems.conclusionsSectionareVcontainedcontainsinaThomasJ.L.HellersteinisaResearchStaffMemberhellers@us.ibm.comJ.WatsonResearchCenter,Hawthorne,NewatYork,theU.S.A.

IBMServers󰀀

Edge󰀀Servers󰀀

HTTP󰀀Application󰀀Servers󰀀

Database󰀀Servers󰀀

Fig.enclosed1.Exampleofamulti-tieredeCommercesystem.Servertiersareareindicatedindashedbythelines.arrows.

TheflowanddensityofrequestsandresponsesII.STRUCTUREOFCOMPUTINGSYSTEMS

tems.ThiseCommerceOursectionfocusintroducesisenterprisekeyconceptsincomputingsys-systemFigureInternet.such1displaysSystems.

levelcomputing,especiallyasthosethethatgeneralprovidestructureofaneCommercependeachontheEnd-to-endflowofrequestsservicelevelson-lineacross(e.g.,responsestorefrontstimes)onthede-isTheorganizedofwhichintohasmultipleitsownmultipletiersofservers,groupscomplexstructure.ThesystemandServersroutesfirsttier,themthetoEdgeofservers,calledtiers.theHypertextServers,acceptin-comingrequestsSome(thesecondtier)whereTransferrequestsProtocolare(HTTP)processingfractionoftheserequestsrequiremoresophisticatedinterpreted.(theandsoareforwardedtoanApplicationServeraccessthirdtier).Theprogramsthatexecuteheremayrequiretier).

tostructureddatainaDatabaseServer(thefourthApplicationEachsoftwareelement(e.g.,EdgeServer,HTTPServer,ture.Forexample,Server,theDatabaseRApplicationServer)Serverhasahascomplexanoperatingstruc-system(e.g.,UNIX1JavainmorewhichVirtual),aJavaexecutionenvironment(thespecialMachine),servletaservletcontainer(anenvironmentrequireservlets.resourcesvariousTheseresourcescomponentsprogramsexecute),andoneortodotheiroftheApplicationServerandarememory,thecentralprocessingwork.ExamplesunitofofContentionoperatingforsystemresourcesprocesses.

(CPU),isaofrobustproblems.resourcescomputingForcanexample,resultsystemscentralconcerninthedesignintooperformancesincethelimitedavailabilitylittlememoryand/orallocatedavailabilityto

1UNIX

isaregisteredtrademarkofTheOpenGroup.

100Autonomic ManagerSLA Cost in %80

60Analyze󰀀Knowledge󰀀Plan󰀀40

20

Monitor󰀀Execute󰀀0

−200204060Sensor󰀀Effector󰀀Hours of Downtime

Fig.2.Staircasefunctionofcostsinaservicelevelagreementasreportedin[1].

Fig.3.

Resource󰀀theJavaVirtualMachinecanresultinexcessive“garbagecollection”wherebydataaremovedinordertocompactunallocatedstoragetocreatelargerblocks.Resourcecontentionarisesintwoways.Thefirstisaresultofcompetitionbetweencomponentsofasystem.Forexample,theoperatingsystemmaycompetewiththeJavaVirtualMachineformemory.Asecondwayinwhichcontentionarisesisaresultoftheresourcerequirementsofconcurrentrequestsmadetothecomputingsystem.Forexample,a“checkprice”requestmadebyoneend-usermaycompetewithan“orderstatus”requestmadebyanotherend-userforJavathreads,memory,anddatabaseconnections.Increasingly,servicelevelobjectives(SLOs)areusedtospecifythedesiredresponsetimes,throughputs,and/orothermetricsdesiredfordifferentrequeststothecomputingsystem(e.g.,“orderstatus”,“buyitem”,“checkprice”).Forexample,abookstorethatoutsourcesitscomputingsystemsmighthavethefollowingSLO:“orderstatusrequestsshouldhavearesponsetimethatisnogreaterthan1second.”ThesetofSLOsusedbyaninstallationisreferredtoasaServiceLevelAgreement(SLA).SLAsmayspecifypenal-tiesifthecontractedserviceisnotdelivered.Forexample,Figure2plotsthepenaltyforexcessivedowntime(withareward,ornegativecost,forgreatlyreducingdowntime)thatisexpressedintermsofthepercentofthecustomer’smonthlyservicecharge[1].Onecanviewtheproviderofcomputingservicesasassigningresources(e.g.,servers)inawaysoastominimizethesumofresourcecostsandSLApenalties.NotethatnotallservicerequestsarecoveredintheSLA.ThoserequeststhatarenotcoveredbytheSLAareservedona“besteffort”basis.Further,sincerequestsmayflowthroughmanyserversandcomponentswithintheserver,itcanbecomplicatedtodeterminehowtomanageresourcesinawaysothattheSLOsarenotviolated.OnesoftwarestructureformanagingresourcestoachieveSLOsistheautonomiccomputingframework[2].Asde-pictedinFigure3,anautonomicmanageraccessesre-sourcesthroughtheirsensorstoobtainmeasurementdataandinteractswithresourceeffectors(oractuators)toComponentsoftheAutonomicComputingArchitecture.

changethebehavioroftheresource.Themanagercon-tainscomponentsformonitoring,analysis,planning,andexecution.Commontoalloftheseisknowledgeofthecomputingenvironment,servicelevelagreements,andotherrelatedconsiderations.Theautonomicmanagermonitoringcomponentfiltersandcorrelatessensordata.Theanalysiscomponentprocessestheserefineddatatodoforecastingandproblemdetermination,amongotheractivities.Planningconstructsworkflowsthatspecifyapartialorderofactionstoaccomplishagoalspecifiedbytheanalysiscomponent.Theexecutecomponentcontrolstheexecutionofsuchworkflows.III.CONTROLPROBLEMSThissectiondescribesseveralcontrolproblemsincom-putingsystems.Manyoftheseproblemsarisefromkeytechnologyandbusinesstrendsthatareshapingthedirec-tionofcomputing.Thesetrendsare:(1)therisingcostofoperatingcomputingsystems;(2)theon-demandmodelforacquiringITproducts;(3)theincreasinguseofoutsourcingtosatisfytheITrequirementsofbusinesses;and(4)thewide-spreaduseoftheInternettoconnectbusinesseswiththeircustomers.Whilethesetrendshavebeenon-goingforsometime,onlynowisthereemergingarealizationoftheimportanceofcontrolengineeringinaddressingthemWebeginwiththecostofoperatingcomputingsystems.Forsometime,ithasbeenrecognizedthatwhilehardwareandsoftwarepriceshavedeclineddramatically,thecostofoperatingcomputingsystemsremainslargeandisincreas-ing.Includedhereiswhatisneededtoensurereliability,security,andgoodperformance.Industryanalystsestimatethatthesecostsaccountsfor60%to90%ofthetotalcostofownership(e.g.,[3]),largelybecauseoftheamountofhumaninvolvementrequiredforsystemoperation.Onepartofthecostofoperationsisconfiguringsoftwaresystems(oftenconsistingofmultipleproducts),ataskthatofteninvolvesadjustinginternalcharacteristicssuchasbufferpoolsizesandnumberofconcurrentthreads.Inessence,2

theseinternalcharacteristicsaretheeffectorsbywhichthesystemiscontrolled.Unfortunately,itisraretohaveadirectrelationshipbetweenthesettingsofresourceeffectorsandthevaluesofmetricsrelatedtoSLOs(e.g.,responsetimes).Thus,humanexpertsareoftenneededtotranslatebetweentheunitsofresourceeffectorsandSLOmetrics.DoingsorequirespeoplewithconsiderableexpertiseandhenceincreasesthecostofdeliveringITservices.Controltechnologycanhelpbyautomatingthistranslationsothatresourceeffectorsoperateintheunitsusedinservicelevelobjectives.Forexample,[4]describesasysteminwhichadministratorsspecifyservicelevelobjectivesinsteadofdetailsofmemoryallocations,CPUpriorities,andotherconfigurationparameters.Anotherreasonforthehighcostofoperatingcomputingsystemsisthatsincetheyarecomplexnon-linearsystemsitisdifficulttooptimizetheirperformance.Oneofthemostcommonwaysinwhichthisoptimizationisdoneisbyloadbalancing,atechniquewherebyrequestsaredistributedacrossresourcesinawaythatequalizesloads.Forexample,theEdgeServerinFigure1isresponsiblefordistributingincomingrequeststoHTTPServersinawaythatbalancestheloadontheseservers.Loadbalancingtendstoreduceresponsetimesandincreasethroughputssincetheperformanceofcomputingsystemsisusuallydeterminedbythemostheavilyloadedresource(oftenreferredtoasthebottleneckresource).Thisisanoptimizationproblemforwhichtheobjectivefunctionistominimizethediffer-enceinutilizationoftheresources.Controltechniquesareparticularlyusefultoaddressthedynamicsofthesystem.Forexample,[5]describesasysteminwhichmemoryresourcesarebalancedinadatabasemanagementsystemwithconsiderationsforchangesinthequeriesmadetothesystem.AsecondtrendistheinterestoflargercustomersinanewmodelforacquiringIT.Traditionally,customerspurchasecomputingcapacitywellinadvanceofitsusage.Thisprovideslittleflexibilitytoaddcapacityifloadsincreaseunexpectedlyortosavemoneybysheddingunneededcapacity.Recently,therehasbeenmuchinterestinprovidingcomputingcapabilities“on-demand”ratherthanpurchasingthemoutright.Thiscouldbedoneinthecontextofout-sourcingwherebytheoutsourcer(sometimesreferredtoasthecomputingutility)suppliesthelevelofresourceneededandthecustomerischargedaccordingly.Alternatively,itcouldbethattheequipmentpurchasedbyacustomerhasmeteringcapabilitythatthesellerreadstodeterminemonthlychargestothecustomer(muchlikeawaterorelec-tricalmeter).Implementinganon-demandsystemrequiresacapabilitytoprovisionresourcesdynamicallytosatisfynewdemandsaswellasanabilitytode-provisionresourcesdynamicallyiftheyarenolongerneeded(e.g.,[6]).Aswithloadbalancing,thisisanoptimizationproblem.However,ithasverydifferentcharacteristicsfromloadbalancingintwoways:(a)abusinessleveloptimizationisemployedintermsofminimizingthesumofthecostofholdingcostsofTABLEI

SUMMARYOFTHECONTROLPROBLEMSINCOMPUTINGSYSTEMS

DISCUSSEDINTHISARTICLE.

ControlProblemTranslateeffectorunitsOptimizeresourcesRegulateserviceRejectdisturbancesDescriptionTranslatebetweenSLOmetricsandtheunitsusedbyeffectorsofcomputingsystems.

Balanceloadstominimizebottlenecksandprovisiontominimizecosts.AdjustresourceusagesothatservicelevelsareconsistentwithSLOs.

Regulateinthepresenceoflargechangesinloadsandresourcefailures.

serversandpenaltiesforviolatingSLOsinanSLA;and(b)oftenprovisioningandde-provisioninghavedead-times,acharacteristicthatcomplicatescontrollerdesign.AthirdtrendisIToutsourcing.Becausespecializedskillsarerequiredtooperatecomplexcomputingenvironments,manycustomersarechoosingtooutsourcetheirITneeds.OutsourcingmeansthatanorganizationsuchasEDSorIBMprovidetheITequipmentandskilledprofessionalstooperatetheseequipment.Thisrequiresthattheout-sourcedcustomerspecifyaservicelevelagreement(SLA)thatquantifiestheserviceexpectedfromtheoutsourcingorganization.Thus,theoutsourcerneedsawaytoenforceSLAssothatcustomerswhopayforhighergradesofservice(e.g.,lowerresponsetimes)receivetheirexpectedlevelofservice.Thatis,theremustbeawaytoregulatethelevelofservicedelivered.Incontrolterms,thisisaregulationproblem.ThelasttrendisthatbusinesseshaveapresenceontheInternet,bothtosupplyinformationaboutthecom-paniesgoodsandservicesandtosellthesegoodsandservices.WhilethebroadreachoftheInternethasgreatappealforbothofthesegoals,itcreateschallengesaswell.Inparticular,websitesaresubjecttoflash-crowds,aphenomenawherebyloadsgrowdramatically(e.g.,asaresultofpoliticalorweatherevents)[6].Thus,ithasbecomeessentialforITsystemstodealwithloadsthatcanincrease(ordecrease)withinsecondsorminuteswhilestillcomplyingwithSLAs.Incontrolterms,thisisadisturbancerejectionproblem.OurcharacterizationofcontrolproblemsinsummarizedinTableI.IV.CONTROLANALYSISANDDESIGNThedesignandanalysisofcontrolsystemsforcomputingsystemsrequiresmodelsoftheresourceoperation,appro-priatesensorsandeffectors,andconsiderationsforthefullsetofelementsinthecontrolloop(e.g.,controller,filter,parameterestimator).Thissectionaddresseseachofthesetopics.3

1CPU0.5

MEM01020}100λ󰀀1󰀀K-mµ10.5M󰀀λ󰀀mµ1001000Fig.6.M/M/m/K/Mqueueingmodel.ThethinktimeoftheMcustomersisexponentiallydistributedwiththerateλ.Theservicetimesofthemserversisexponentiallydistributedwiththerateµ.

MCKA5001.5Time (s)

Response Time00500100015001Fig.4.models.

PredictionsofCPUandmemoryutilizationsusingtwoSISO

CPU10.50.5MEM010.500200BOPSFig.7.FitofM/M/3/140/140modeltodatafromathreeservertestbedrunninganeCommerceworkload.

020KA100100050000500Time (s)10001500Fig.5.PredictionsofCPUandmemoryutilizationsusingasingleMIMOmodel.

thecompletingofthelastrequestonthatconnection.Weconsidertwomeasuredoutputs,theutilizationoftheCPU(denotedbyCPU)andtheutilizationofmemory(denotedbyMEM).OnewaytomodeltheeffectofMaxClientsandKeepAliveonCPUandMEMistoconstructtwoSISOmodels.WhileMaxClientsaffectsbothCPUandMEMKeepAliveonlyaffectsCPU.Thus,weusethemodelsyCPU(k)yMEM(k)=aCPUyCPU(k−1)+bCPUKA(k−1)=aMEMyMEM(k−1)+bMEMMC(k−1)A.ModelingtheManagedElementTheconstructionofsystemmodelsremainsasignificantchallengeinthesuccessfulapplicationofcontroltheorytocomputingsystems.Fourapproachesareusedinpractice.Thefirstisapurelyempiricalapproachthatemployscurvefittingtoconstructmodels;thesemodelsdonotaddressdynamics.ThishasbeenveryeffectiveinIBM’smainframesystems[4].ItsapplicationtosystemssuchasFigure1isbeinginvestigated.Thesecondapproachtomodelingisablackboxmethod-ologythathasbeenappliedtoSISOandMIMO(multipleinputmultipleoutput)systems(e.g.,[7],[8]).Thisapproachrequires:choosinganoperatingpoint,designingappropriateexperiments,anddevelopingempiricalmodels.Typically,ARXmodelsareusedsuchasy(k)=a1y(k−1)+···+any(k−n)+b1u(k−1)+···+bmu(k−m),wherem≤n.Forexample,intheApacheHTTPServer,therearetwocontrolinputs,themaximumnumberofclients(denotedbyMaxClients)thatcontrolsthelevelofconcurrency,andthekeepalivetimeout(denotedbyKeepAlive)thatspecifieshowlongaconnectiontotheserverpersistsafterMCFigure4showstheresults.WeseethatthefitforMEMisquitegood.However,themodelofCPUispoorasMaxClientsischangedfromitsoperatingpoint.AnalternativeistheMIMOmodely(k)=Ay(k−1)+Bu(k−1)󰀁󰀂whereyT=CPUMEM,Ais󰀂a2×2matrix,Bisa󰀁T1×2matrix,andu=KAMC.Figure5displaystheresultsoftheMIMOmodel.WeseethattheMIMOmodelisconsiderablymoreaccuratethanthemultipleSISOmodel.Athirdapproachtomodelingisbasedonstochasticprocesses,especiallyqueueingtheory.Bymakingassump-tionsaboutthedistributionofinter-arrivaltimesandservicetimes,queueingtheoryprovidesawaytocalculatetheeffectofcontrolinputssuchasbuffersize,numberofservers,andserviceratesonmeasuredoutputssuchasresponsetimesandthroughputs.Figure6depictsanM/M/m/K/MqueueingsysteminwhichthereareMcustomers,abufferoflengthK−m,andmservers.TheMcustomersthink4

foranexponentiallydistributedperiodoftimewithrateλ,atwhichpointtheysubmitarequest.Therequestisassignedtoanidleserver,ifoneexists,andservicetakesanexponentiallydistributedtimewithrateµ.Ifthereisnoidleserver,therequestisplacedattheendofthequeuewhereitwaitsuntilthoserequestsinfrontofithavebeenserved.Ifthequeueisfull,therequestisdiscardedandthecustomerwaitsforanotherexponentiallydistributedtime1withmeanλ.

WeassessedtheadequacyofthismodelinthecontextoftheHotRodsystemforaneCommerceworkload[6].Theintensityoftheworkloadismeasuredinbusinessoperationspersecond(BOPS),andservicequalityisquantifiedintermsofresponsetime.Figure7comparesthemeasuredresponsetimesobtainedfromtheHotRodsystemwiththoseestimatedbyanM/M/m/K/Mqueueingsystem,wherem=3andM=140.(Withfirst-come-first-servedscheduling,itisstraightforwardtoestimateresponsetimesfromtheMarkovstatemodelofM/M/m/K/M.)Thedotsaremeasuredresponsetimes,andthesquaresaretheresponsetimesestimatedbythemodel.Thefitisquitegoodinthatthemodelaccountsforover90%ofthevariabilityinthedata.Further,itisrelativelyeasytomodeltransientbehaviorusingtheMarkovchain,whichhasappealforcharacterizingtheeffectsofcontrolactions.AshortcomingofthemodelisthatitisnotclosedforminthatitssolutionrequiresconstructingandanalyzingaMarkovchain.Simpleropenqueueingmodelsthatassumeaninfinitenumberofcustomers(i.e.,M=∞)oftenhaveaclosedformsolution.Unfortunately,thesemodelshaveapoorfittotheHotRoddata.

Afourthapproachtomodelingistodevelopspecialpurposerepresentationsofspecificsystems.Anexampleofthisisthefirstprinciplesanalysisdoneforadaptivequeuemanagementinnetworkrouters[9].ThisapproachinvolvesadetailedunderstandingoftheTCP/IPprotocolandthedevelopmentofdifferentialequationstoestimateatransferfunction.B.Sensors

Asignificantfocusinthemanagementofcomputingsystemsisthechoiceofsensors,especiallystandardizinginterfacestosensors.ThemostwidelyusedprotocolforaccessingsensordataincomputingsystemsistheSimpleNetworkManagementProtocol(SNMP)[10].Whilethisallowsforprogrammaticaccess,ithasnotaddressedvariousissuesthatareofparticularconcernforcontrolpurposes.Amongthesearethefollowing:

1)Typically,therearemultiplemeasurementsources(evenonasingleserver)thatproducebothintervalandeventdata.Unfortunately,theintervalsareoftennotsynchronized(e.g.,10secondvs.1minutevs.1hour),andmissingdataarecommon.Evenworse,datafromdifferentserversoftencomefromclocksthatareunsynchronized(orworsestill,aresynchro-nizedviasomecomplexprotocolthatconvergesover

2)

3)

4)

5)

alongerwindow).

Often,themetricthatitisdesirabletoregulateisnotavailable.Forexample,end-to-endresponsetimesarenotoriouslydifficultandexpensivetoobtain.Thus,surrogatemetricsareoftenusedsuchasCPUqueuelength.Hence,itmaywellbethatthesurrogateiswellregulatedbutthedesiredmetricisnot.

Therecanbesubstantialoverheadsassociatedwithmetriccollection.Forexample,itcanbequitein-formativetocollectinformationabouttheresourceconsumptionofindividualrequeststoawebserver.HoweverdoingsomayconsumeasubstantialfractionoftheserverCPU.Thisresultsinanotherkindofcontrolproblem—determiningwhichmeasurementstocollectandatwhatfrequency.

Often,themeasurementsystemhasbuilt-indelays.Forexample,responsetimescannotbereporteduntiltheworkunitcompletes.Sometimes,themeanre-sponsetimeisaboutthesameasthecontrolinterval,whichcanleadtoinstabilities.Unpredictabledelaysarecommonaswellsincemeasurementcollectionistypicallythelowestprioritytaskandsoisdelayedwhenhighpriorityworkarrives(whichcanbeacriticaltimeforthecontroller).

Anon-goingchallengefordevelopersofinstrumen-tationforcomputingsystemsisthatthereisawidevariationinthesemanticsofsupposedlystandardmetrics.Forexample,themetric“pagingrate”couldmeananyofthefollowing:(a)therateatwhichpagesarewrittentodisk;(b)therateatwhichpagesarereadfromdisk;and(c)therateatwhichpage-insarerequested(notallofwhichresultinaccessingsecondarystorage).Becauseofthesedisparities,anattempthasbeenmadetostandardizethedefinitionofmetrics[11].However,thiseffortislimitedtoUNIXOperatingSystemssincetheyhaveasimilarstructureandhencesimilarmetrics.

C.Effectors

Oneofthemorechallengingproblemsinthecontrolengineeringofcomputingsystemsisthatthesetofavail-ableeffectors(actuators)oftenhasasomewhatcomplexrelationshipwiththemeasuredoutput,especiallyintermsofdynamics.Weillustratethisproblembygivingseveralexamples.

ConsidertheIBMLotusDominoServer,anemailserver.Oneobjectiveofconsiderableinteresttoadministratorsistocontrolinternalqueueing,bothforreasonsofrelia-bility(e.g.,sothatcertainload-dependentexceptionsdonotoccur)andperformance.Thatis,administratorswanttolimitthenumberofuserswhoserequestsarebeingprocessedconcurrently.Werefertothisasthenumberofconcurrentusers.Commonly,administratorsusetheeffectorMaxUsers,aparameterthatlimitsthemaximumnumberofusersthatareconnectedtothesystem.However,thenumberofconnectedusersisnotthesameasthenumber

5

ofconcurrentusers.Forexample,duringlunchtime,theremaybemanyconnectedusers,veryfewofwhomsubmitrequests.Underthesecircumstances,MaxUserscouldbemuchlargerthanthenumberofconcurrentusers.Ontheotherhand,duringbusyperiods(e.g.,closetoanend-of-monthdeadline),almostallconnectedusersmayhavesubmittedrequests.Inthiscase,MaxUsersmaybeveryclosetothenumberofconcurrentusers.Inessence,thegainassociatedwiththiseffectorisloaddependent.ThereisstillanothercomplicationwithMaxUsers.Themechanismemployeddoesnotmaintainaqueueofwaitingrequeststoconnecttotheserver.Thatis,ifMaxUsersisincreased,thereisnoeffectuntilthenextrequestarrives.Ifrequestsareofshortdurationandaremadequickly,thereislittledelay.However,ifrequestsoccuratalowerrate,thenthiseffectorintroducesadeadtimethatmakescontrolmorechallenging.AnotherexampleofacomplexeffectoristhenicecommandusedinUNIXsystems.niceprovidesawaytoadjustthepriorityofaprocess,somethingthatisespeciallyimportantifthereisamixtureofCPUintensiveandnon-CPUintensiveworkinthesystem.Intheory,nicecanbeusedtoenforceSLOsdealingwiththefractionoftheCPUthataprocessreceives.However,thisturnsouttobecomplicatedtodoinpracticebecauseofthewayniceaffectspriorities.Asshownin[12],thisisnon-linearrelationshipthatdependsonthenumberofprocessescompetingfortheCPUaswellastherangeofprioritynumbersused.Recognizingthelimitationsofusingnice,specialpurposeschedulershavebeendeveloped(e.g.,[13]).Inessence,theseapproachescreateanew,morerationalsetofeffectors.Afinalexampleisthestart-timefairqueueing(SFQ)algorithm.Thisresourcemanagementalgorithmcontrolstheservicedeliveredbyaresourcebycontrollingthepriorityassignedtoincomingrequests[14].Specifically,SFQoperatesbytaggingincomingworkbyclass,andthetagsdeterminetheprioritybywhichtherequestisprocessed.Unfortunately,thismechanismhassomesubtle,load-dependentcharacteristicsthatcreatechallengesfordesigningcontrolsystems.Inparticular,changingthetagassignedtoanewrequesthasnoeffectuntiltherequestsaheadofithavebeenprocessed.Ifloadislight,therewillbefewsuchrequests,andsolittledeadtime.However,ifloadsareheavy,deadtimescouldbesubstantial.Ifdeadtimescanbepredicted,thencompensationmightbepossible.Otherwise,thecontrolperformanceofthiseffectorcanbeimpaired,possibilityevenresultinginstabilityproblems.D.ControlSystemsThissectiondescribesissuesoftenencounteredinthedesignofclosedloopsforcomputingsystems.Webeginbyobservingthatwherecontroltheoryhasbeenappliedtocomputingsystemsverysimplecontrollershavebeenused.Forexample,aPIcontrollerisusedin[15],[16],and[17].Anevensimplerintegralcontrollerisusedin[7].NotesServer

R(z)+E(z)−zKIz −1U(z)0.47z −0.43Y(z)Fig.8.Server.

BlockdiagramforintegralcontroloftheIBMLotusDomino

Inalmostallcases,theclosedloopsystemissingleinputsingleoutput(SISO).Anaturalwaytoapplycontroltheoryistoaregula-tionproblem,suchasmaintainingservicelevelobjectives(SLOs).Forexample,aneCommercesitesuchasFigure1mayprovidedifferentSLOsforresponsetimedependingonthetypeofinteraction(e.g.,“buy”versus“browse”).Afirstthoughtistoregulateresponsetimesdirectly.However,thereisanissuehere.Ifloadislight,theeCommercesitecanprovideservicethatismuchbetterthantheSLO.And,ifloadisheavy,thenitmaybethatnoneoftheSLOscanbesatisfied.Onewaytoavoidthisconundrumistoregulatetherelativeperformanceofthedifferentkindsofrequests.Thatis,non-negativefractionsH1,···,Hnareselectedforeachkindofrequest,sothatH1+···+Hn=1.TheregulationproblemistomakeDi/(D1+···+Dn)=Hi,whereDiisthedelayincurredbythei−thkindofrequest.Thisideaisdevelopedin[18]andappliedtodifferentiatedcachingservices.Suchanapproachworksbestinoverloadsituations(whichiswherecontrolismostimportant).Thisbeingthecaseandassumingthatservicetimesaresmallcomparedtodelays,itcanbeareasonableapproachforregulatingrelativeresponsetimesaswell.Theremainderofthissectiondescribestwoexamplesofdesigningclosedloopsystemsforcomputingsystems.Thefirstexamplerelatestothenatureofmeasurementsensors.Thedynamicsofthemeasurementsystemarealmostneverconsideredinqueueinganalysesofcomputingsystems,inlargepartbecausethefocusisonsteadystate.However,thesedynamicscanbeplayamajorroleincontrolperformance.Toillustratetheforegoing,considertheIBMLotusDominoServer.Thecontrolproblemweaddressisreg-ulatingthenumberofconcurrentusersbymanipulatingtheMaxUserseffector(whichcontrolsthenumberofconnectedusers).SystemidentificationoftheIBMLotusDominoServerdeterminedthatthetransferfunctionfromMaxUserstoconcurrentusersisN(z)=0.47z−0.43

(See[7]fordetails.)Figure8displaysthecontrolsystemconsideredinwhichintegralcontrolisused.Thetransferfunctionfromthereferenceinputtothemeasuredoutputis

F(z)=

Y(z)zKI(0.47)=R(z)(z−1)(z−0.43)+zKI(0.47)

(1)

6

MaxUsers(k) RIS(k), r(k)100Parameter Estimator󰀀

50020002000400060008000100001000Reference󰀀Input−󰀀ControllerServerFilterMeasured󰀀Output+󰀀0200040006000800010000 k

Fig.9.StepresponseoftestbedforthecontrolsystemfortheIBMLotusDominoServerdescribedinFigure8.

NotesServer

NotesSensor0.17z-0.11z −0.Fig.11.Server.BlockdiagramofanadaptivecontrollerfortheApacheHTTPParameter󰀀Estimator󰀀

R(z)+E(z)−zKIz −1U(z)0.47z −0.43Y(z)Filter 2

Fig.10.BlockdiagramofintegralcontroloftheIBMLotusDominoServerthatexplicitlymodelsthesensor.

Reference󰀀Input−󰀀ControllerServerMeasured󰀀Output+󰀀Howwelldoesthiscontrolmodeldescribethebehavioroftherealsystem?Toanswerthisquestion,atestbedwasdevelopedandexperimentswereconductedtoassessthestepresponsetoachangeinthereferenceinput.Figure9displaysthestepresponsetoachangeinthereferenceinputthatoccursaroundtime3800forKI=0.1.Thefigurecontainstwoplots,oneforthenumberofconcurrentusers(denotedbyRIS(k))andasecondplotthatshowstheassociatedvalueofMaxUsers(k).Whilethestochasticsofthesystemmakeitdifficulttoestimatesettlingtimesprecisely,itseemsthatthesettlingtimeisabout300.However,ifKI=0.1thedominantpoleofEquation(1)is0.91.UsingafirstorderapproximationofEquation(1)anddefiningsteadystateasbeingwithin2%ofthefinalvalueofthestepresponse,thenthesettlingtimeofEquation(1)is43.Thisisalmostafactoroftendifferencefromtheactualsettlingtime.Whyistheforegoingestimatesoinaccurate?Theanswerliesinthefactthatwedidnotconsiderthecompletecontrolsystem.Inparticular,wedidnotmodelthesensor.Figure10extendsFigure8toincludetheeffectofthesensor.ThetransferfunctionfromthereferenceinputtothemeasuredoutputofthissystemisG(z)=whereD(z)=(z−1)(z−0.43)(z−0.)+zKI(0.47)(0.17z−0.11)AtKI=0.1,thedominantpoleis0.99.Againusingafirstorderapproximation,thiscorrespondstoasettlingtimeof287,aresultthatisconsistentwithFigure9.Oursecondexampleofacontrolsystemaddressestheuseoffiltersasdescribedin[19].Figure11displaysablockdiagramofanadaptivecontrolschemeforthe1−αApacheHTTPServer.AfilterwithZ-transformz−αisinsertedaftertheservertosmooththestochasticsofthe

Filter 1

Fig.12.BlockdiagramofanadaptivecontrollerfortheApacheHTTPServerinwhichseparatefiltersareusedfortheparameterestimatorandthecalculationofthecontrolerror.zKI(0.47)(0.17z−0.11)Y(z)=R(z)D(z)(2)system.Therearetworeasonsforthis.Thefirstisto

avoidhavingthecontrollerrespondtonoise.Thesecondisthatadaptationprovidedbytheparameterestimatorshouldbasedonlong-termchangesinthemeasuredoutput,notshort-termtransients.

However,thereisaproblemwiththisdesign.Ifweuseamoderatevalueofα,sayα=0.5,thensettlingtimeislong,3.5minutes.Reducingαto0.3reducessettlingtimeconsiderably,butitalsoincreasesthevariabilityofthemeasuredoutputduetoexcessivelyrapidadaptationofparameters.Theissueisthatthecontrollerneedstooperateinsecondsorminutes,whichrequiresasmallerα.However,thetimeconstantoftheparameterestimatorshouldbeintensofminutes,whichdemandsalargerα.Theresultisthatweeitherendupwithverylongsettlingtimesorhighlyvariableparameterestimates.

TheseconsiderationsledtothedesigninFigure12inwhichseparatefiltersareusedforthecontrollerandtheparameterestimator.Filter1,whichisusedtosmoothcontrolleroutput,hasα=0.3.Filter2,whichisusedforparameterestimation,hasα=0.5.Thenewdesignreducessettlingtimeswithoutasubstantialchangeinoutputvariability.

V.RELATEDWORK

Sincetheearly1990s,therehasbeenbroadinterestintheapplicationofcontroltheorytocomputingsystems,especiallyintheareasofdatanetworksoperatingsystems,middleware(e.g.,webservers,databaseservers),multi-media,andpowermanagement.Below,wesummarizethese

7

efforts.Intheareaofdatanetwork,therehasbeenconsiderableinterestinapplyingcontroltheorytoproblemsofflowcontrol.Oneofthefirst,[20],developstheconceptofaRateAllocatingServerthatregulatestheflowofpacketsthroughqueues.Othershaveappliedcontroltheorytoshort-termratevariationsinTCP(e.g.,[21])andsomehaveconsiderstochasticcontrol[22].Morerecently,therehavebeendetailedmodelsofTCPdevelopedincontinuoustime(usingfluidflowapproximations)thathaveproducedinterestinginsightsintotheoperationofbuffermanagementschemesinrouters(see[17],[9]).TheareaofAsynchronousTransferMode(ATM)Networkshasbeenanareaofintensiveexploitationofcontroltheoryinthe1990s(e.g.,[23],[24],[25],[26],[27],[28]).However,thelimitedsuccessofATMtechnologyandtheuseofcontinuoustimeand/oradvancedcontroltechniques(e.g.,stochasticcontrol),meantthattherewaslittleadoptionofcontroltheorybycomputingpractitioners.Althoughnotnearlyasprodigious,therehasbeencon-siderableinterestinapplyingcontroltechniquestooper-atingsystemsaswell.[4]describesthedetailsofcontroltechniqueswidelyusedinIBM’sMultipleVirtualStorage(MVS)operatingsystemtoachieveseveralkindsofservicelevelobjectives.Theforegoingisprimarilybasedonde-tailedknowledgeoftheoperatingsystem’scontrolinputsandmeasuredoutputs.Othershaveproposedapproachesthatrequirelittleknowledgeofdetails,relyinginsteadonlearningalgorithms(e.g.,[29]).Oneofthemostrecentareasinwhichcontroltheoryhasbeenappliedistomiddleware.Middlewarearesoftwaresystemsthatfacilitatethedevelopmentofrobust,enterpriselevelapplications.Examplesincludeapplicationservers(e.g.,theApacheHTTPServer),databasemanagementsystems(e.g.,IBM’sUniversalDatabaseServer),andemailservers(e.g.,theIBMLotusDominoServer).Therearethreetypesofcontrolproblemsthataretypicallyaddressed.Thefirstistoprovideacapabilityforenforcingservicelevelagreementsinthatcustomersreceivetheservicelevelsforwhichtheycontracted.Oftenreferredtoasservicedifferentiation,thisisachievedbyenforcingrelativedelays[15],preferentialcachingofdata[18],orinspecialcasesmodifyingapplicationcodestoinserteffectors(e.g.,[30]).Asecondproblemistoregulateresourceutilizationssothattheyarenotexcessive,eitherbecauseofreliabilityconsider-ations(e.g.,somesoftwaresystemsbecomefragileatheavyloads)orbecauseofsystemdesign(e.g.,toallowsparecapacityforfailovers).ExampleshereincludeamixtureofqueueingandcontroltheoryusedtoregulatetheApacheHTTPServer[31],regulationoftheIBMLotusDominoServer[7],andmultiple-input,multiple-outputcontroloftheApacheHTTPServer(e.g.,simultaneousregulationofCPUandmemoryresources)[8].Thethirdproblemthatisoftenaddressedistooptimizethesystemconfiguration,suchastominimizeresponsetimes[32].Managementofmulti-mediastreamshasalsobeenanareaoffocusforapplyingcontroltheorytocomputingsystems.Thechallengehereisthatend-userperformanceisrelatedtoreceivinganregularflowofcorrelatedstreamsofdata(e.g.,voiceandvideo)whereastheunderlyingsystemsoperatemoreonacontentionbasis(e.g.,executionpriority).Onesolutiontothisistoregulateprocessprioritiesinaccordancewiththedesiredservicelevels(e.g.,[33]).Anotherapproachistodevelopacontrolframeworkinwhichtobuildthecapabilitiesforprovidingtheseservicelevels(e.g.,[34]).Thereisonelastareawementioninpassing—dynamicpowermanagement.Theexpenseandengineeringcompli-cationsassociatedwithsupplyingpowertocomputationalelementshasmotivatedintensiveinvestigationsintohowpowercanbemanagedwithincomputingelements.Con-siderationshereincludeaddressingnonstationaryservicerequests[35],thesuccessofwhichlargelydependsonbeingabletomodeldynamics.Moreextensivediscussionsofpower-awarecomputingcanbefoundin[36]andrelatedarticlesinthesameissue.Thereisavastliteratureonloadbalancing,includingitsuseinmultiplesourcerouting[37],implementationsforL4switches[38],techniquesforbalancingloadsindatawarehouses[39],andredirectionalgorithmsforweb-serversystems[40].Therehavealsobeenstudiesthatanalyzegeneralstrategies,especiallystaticloadbalancing(whichmakesuseoflong-termtrends)versusdynamicloadbalancing(whichexploitscurrentchangesinstate)[41].Weclosethisdiscussionbypointingtoanoverviewoftheapplicationofcontroltechniquestocomputingin[42]andrelatedarticlesinthesameissue.VI.CONCLUSIONSThereareseveralcommonlyoccurringcontrolproblemsincomputingsystems—translatingbetweenserviceorientedunits(e.g.,responsetimes)andeffectorunits(e.g.,themax-imumnumberofconnectedusers),optimizingresources,regulatingservicelevels,andrejectingdisturbances(e.g.,variationsinworkloads).Developingcontrolsystemstoaddresstheseproblemsinvolvesanumberofchallenges.Modelingthemanagedelement(plant)requiresdealingwithstochasticsandnon-linearities.Ourexperience(whichisconsistentwithmanyotherresearchers)isthatsimplermodelsworkbetterinthattheyareeasiertoconstructandtendtobemorerobust.Asecondchallengeisthatsensordataisnoisy,incomplete,andinconsistent.Inpractice,wefindthatsubstantialeffortisoftenrequiredtochangesensorstocorrecttheseshortcomings.Third,effectorshavecomplexeffectsthatoftendonotcorrespondwelltothecontrolobjectives.Again,ourexperienceisthatthesebehaviorsmustbechanged,whichoftenresultsinproductmodifications.Last,thecomputersciencecommunityisoftennaiveaboutwhatconstitutesacontrolsysteminthatthefocusisentirelyonthecontroller.Thatlittleattentionispaidtofilters,thechoiceofmeasuredoutputs,andtime8

delayscanleadtopoorcontrolperformance,especiallylongsettlingtimesand/orsignificantoscillations.Overthelasttwoyears,wehavehadconsiderablesuccessinIBMwithapplyingcontroltheorytocomputingsystems,oftenresultinginsystemsthatoperatemoreconsistentlyandavoidingextremebehaviorssuchaslimitcycles.Thissuccesshasmotivatedustoevangelizetheapplicationofcontroltheorytocomputingsystemsthroughtutorials(e.g.,[43]and[44]),abookoncontroltheoryforcomputerscientists[45],andaclassweareteachingatColumbiaUniversityoncontroltheoryforcomputerscientists(CS6998-4).Ourexperiencetodatehasbeenthatsomeradicalrevisionsareneededinthewaycontroltheoryistaughtinordertomakeitaccessibletothecomputersciencecommunity.Beyondusingexamplesdrawnfromcomputingsystems,weworkentirelyindiscretetime,donofrequencyanalysis,andalmostexclusivelyusepoleplacementdesign.Further,weincludematerialonsystemidentificationsincethisisoneofthemostchallengingaspectsofapplyingcontroltheoryinpractice.Thusfar,theresponsetothisapproachhasbeenquitegood.Wefindthatstudentswithonlyamodestmathematicalbackgroundquicklygraspthekeyconceptsandareabletoapplycontroltheorytodesignproblemsincomputingsystems.REFERENCES

[1]C.Ward,M.J.Buco,R.N.Chang,andL.Z.Luan,“Ageneric

slasemanticmodelfortheexecutionmanagementofe-business,”inThirdInternationalConferenceonE-CommerceandWebTechnolo-gies,Sept.2002.[2]I.B.M.Corporation,“Anarchitecturalblueprint

forautonomiccomputing,”Tech.Rep.http://www-306.ibm.com/autonomic/pdfs/ACwpFinal.pdf,IBMCorporation,2004.

[3]J.HumphreysandM.Melenovsky,“Enablingbusinessagility

throughserverbladetechnology,”Tech.Rep.P508.872.8200,IDC,2003.

[4]J.Aman,C.K.Eilert,D.Emmes,P.Yocom,andD.Dillenberger,

“Adaptivealgorithmsformanagingadistributeddataprocessingworkload,”IBMSystemsJournal,vol.36,no.2,1997.

[5]Y.Diao,J.L.Hellerstein,A.Storm,M.Surendra,S.Lightstone,

S.Parekh,andC.Garcia-Arellano,“UsingMIMOLinearControlforLoadBalancinginComputingSystems,”inAmericanControlConference,June2004.

[6]E.Lassettre,D.W.Coleman,Y.Diao,S.Froehlich,J.Hellerstein,

L.Hsiung,M.R.T.Mummert,G.Parker,L.Russell,M.Surendra,V.Tseng,N.Wadia,andP.Ye,“Dynamicsurgeprotection:Anapproachtohandlingunexpectedworkloadsurgeswithresourceactionsthathaveleadtimes,”inIFIPDistributedSystemsOperationsandControl,Oct.2003.

[7]S.Parekh,N.Gandhi,J.Hellerstein,D.Tilbury,J.Bigus,andT.S.

Jayram,“Usingcontroltheorytoacheiveservicelevelobjectivesinperformancemanagement,”Real-timeSystemsJournal,vol.23,pp.127–141,2002.

[8]Y.Diao,N.Gandhi,J.L.Hellerstein,S.Parekh,andD.Tilbury,

“UsingMIMOfeedbackcontroltoenforcepoliciesforinterrelatedmetricswithapplicationtotheApacheWebserver,”inIEEE/IFIPNetworkOperationsandManagement,April2002.

[9]C.V.Hollot,V.Misra,D.Towsley,andW.B.Gong,“Acontrol

theoreticanalysisofRED,”inProceedingsofIEEEINFOCOM’01,(Anchorage,Alaska),Apr.2001.

[10]A.Tannenbam,ComputerNetworks.PrenticeHall,4thed.,2002.[11]T.O.Group,SystemsManagement:TheUniversalMeasurement

Architecture.TheOpenGroup,1997.

[12]J.L.Hellerstein,“Achievingservicerateobjectiveswithdecayusage

scheduling,”IEEETransactionsonSoftwareEngineering,vol.19,no.8,pp.813–825,1993.

[13]J.KayandP.Lauder,“Afairsharescheduler,”Communicationsof

theACM,vol.31,no.1,pp.44–55,1988.

[14]P.Goyal,H.M.Vin,andH.Cheng,“Start-timefairqueueing:A

schedulingalgorithmforintegratredservicepacketswitchingnet-works,”inACMSIGCOMM,1996.

[15]T.F.AbdelzaherandN.Bhatti,“Adaptivecontentdeliveryfor

WebserverQoS,”inInternationalWorkshoponQualityofService,(London,UK),June1999.

[16]S.Mascolo,“Classicalcontroltheoryforcongestionavoidancein

high-speedinternet,”inProceedingsofthe38thConferenceonDecision&Control,Dec.1999.

[17]C.V.Hollot,V.Misra,D.Towsley,andW.B.Gong,“Ondesigning

improvedcontrollersforAQMrouterssupportingTCPflows,”inProceedingsofIEEEINFOCOM’01,(Anchorage,Alaska),Apr.2001.

[18]Y.Lu,A.Saxena,andT.F.Abdelzaher,“Differentiatedcaching

services:Acontrol-theoreticapproach,”inInternationalConferenceonDistributedComputingSystems,Apr.2001.

[19]R.Zhang,S.Parekh,Y.Diao,andM.Surendra,“Improvingthe

adaptationspeedofaself-managingwebserver,”inPersonalCom-munication,2004.

[20]S.Keshav,“Acontrol-theoreticapproachtoflowcontrol,”inPro-ceedingsofACMSIGCOMM’91,Sept.1991.

[21]K.Li,M.H.Shor,J.Walpole,C.Pu,andD.C.Steere,“Modelingthe

effectofshort-termratevariationsontcp-friendlycongestioncontrolbehavior,”inProceedingsoftheAmericanControlConference,pp.3006–3012,2001.

[22]E.Altman,T.Basar,andR.Srikant,“Congestioncontrolasa

stochasticcontrolproblemwithactiondelays,”Automatica,vol.35,pp.1936–1950,1999.

[23]L.BenmohamedandS.M.Meerkov,“Feedbackcontrolofconges-tioninpacketswitchingnetworks:thecaseofasinglecongestednode,”IEEETransactionsonNetworking,vol.1,Dec.1993.

[24]C.E.Rohrs,R.A.Berry,andS.J.O’Halek,“Acontrolengineer’s

lookatATMcongestionavoidance,”inGLOBECOM,pp.10–1094,1995.

[25]P.JohanssonandA.Nilsson,“Discretetimestabilityanalysisofan

explicitratealgorithmfortheabrservice,”inIEEEATMWorkshop,pp.229–350,1997.

[26]N.S.ShankarandA.Shivaprasad,“AnInstantaneousControlmodel

forFlowControlinanATMNetwork,”inInternationalConferenceonInformation,CommunicationsandSignalProcessing,pp.878–882,1997.

[27]A.Pitsillides,Y.A.Sekercioglu,andG.Ramamurthy,“Effective

controloftrafficflowinatmnetworksusingfuzzyexplicitratemarking(ferm),”JournalonSelectedAreasinCommunications,vol.15,no.2,pp.209–225,1997.

[28]S.Mascolo,D.Cavendish,andM.Gerla,“ATMratebasedconges-tioncontrolusingasmithpredictor:anEPRCAimplementation,”inProceedingsofIEEEINFOCOM’96,1996.

[29]J.Bigus,“Applyingneuralnetworkstocomputersystemperformance

tuning,”inIEEEInternationalConferenceonNeuralNetworks,pp.2442–2447,1994.

[30]S.Parekh,K.Rose,J.L.Hellerstein,S.Lightstone,M.Huras,

andV.Chang,“Managingtheperformanceimpactofadministrativeutilities,”inIFIPConferenceonDistributedSystemsOperationsandManagement,2003.

[31]L.Sha,X.Liu,Y.Lu,andT.Abdelzaher,“Queueingmodelbased

networkserverperformancecontrol,”inIEEERealTimeSystemsSymposium,2002.

[32]Y.Diao,J.L.Hellerstein,andS.Parekh,“Optimizingqualityof

serviceusingfuzzycontrol,”inDistributedSystemsOperationsandManagement,2002.

[33]S.SelvakumarandS.V.Raghavan,“Differentialpriority-based

adaptiverateservicedisciplineforqosguaranteeofvideostream,”ComputerCommunications,vol.20,no.13,pp.1160–1174,1997.[34]B.LiandK.Nahrstedt,“Control-basedmiddlewareframeworkfor

qualityofserviceapplications,”IEEEJournalonSelectedAreasinCommunication,1999.

[35]E.Chung,L.Benini,A.Bogliolo,Y.Lu,andG.D.Micheli,

“Dynamicpowermanagementfornonstationaryservicerequests,”

9

[36][37][38][39][40][41]

[42][43][44][45]

IEEETransactionsonComputers,vol.51,no.11,pp.1345–1361,2002.

M.R.StanandK.Skadron,“Power-awarecomputing,”IEEECom-puter,vol.Dec.,pp.35–38,2003.

L.Zhang,Z.Zhao,Y.Shu,L.Wang,andO.Yang,“Loadbalancingofmultipathsourceroutinginadhocnetworks,”inInternationalConferenceonCommunications,2002.

J.Hyun,I.Jung,J.Lee,andS.Maeng,“Contentsnifferbasedloaddistributioninawebservercluster,”IEICETransactionsonInformationandSystems,vol.E86-D,no.7,2003.

H.Marteins,E.Rahm,andT.Stohr,“Dynamicqueryschedulinginparalleldatawarehouses,”ConcurrencyComputationPracticeandExperience,vol.15,no.11-12,2003.

V.Cardellini,M.Colajanni,andP.S.Yu,“Requestredirectionalgo-rithmsfordistributedwebsystems,”IEEETransactionsonParallelandDistribuedSystems,vol.14,no.4,pp.355–368,2003.

H.Kameda,E.S.Fathy,I.Ryu,andJ.Li,“Aperformancecompar-sionofdynamicvs.staticloadbalancingpoliciesinamainframe–peronalcomputernetworkmodel,”inProceedingsofthe39thIEEEConferenceonDecisionandControl,IEEE,2000.

R.SanzandK.Arzen,“Trendsinsoftwareandcontrol,”IEEEControlSystemsMagazine,vol.June,pp.12–15,2003.

J.HellersteinandS.Parekh,“Anintroductiontocontroltheorywithapplicationstocomputerscience,”inACMSigmetricsTutorial,2001.Y.Diao,J.Hellerstein,andS.Parekh,“Fasttrackintroductiontocontroltheoryforcomputerscientists,”inIEEE/IFIPIntegratedManagement,2003.

J.Hellerstein,Y.Diao,S.Parekh,andD.Tilbury,FeedbackControlofComputingSystems.JohnWiley&Sons,2004(expected).

10