Specification and management of QoS in real-time databases s

Abstract—Real-time applications such as e-commerce, flight control, chemical and nuclear control, and telecommunication are becoming increasingly sophisticated in their data needs, resulting in greater demands for real-time data services that are provided

304IEEETRANSACTIONSONCOMPUTERS,VOL.55,NO.3,MARCH2006

SpecificationandManagementofQoSin

Real-TimeDatabasesSupporting

ImpreciseComputations

¨rgenHansson,Member,IEEE,andSangHyukSon,SeniorMember,IEEEMehdiAmirijoo,Jo

Abstract—Real-timeapplicationssuchase-commerce,flightcontrol,chemicalandnuclearcontrol,andtelecommunicationare

becomingincreasinglysophisticatedintheirdataneeds,resultingingreaterdemandsforreal-timedataservicesthatareprovidedbyreal-timedatabases.Sincetheworkloadofreal-timedatabasescannotbepreciselypredicted,theycanbecomeoverloadedandtherebycausetemporalviolations,resultingindamageorevenacatastrophe.Imprecisecomputationtechniquesaddressthisproblemandallowgracefuldegradationduringoverloads.Inthispaper,wepresentaframeworkforQoSspecificationandmanagementconsistingofamodelforexpressingQoSrequirements,anarchitecturebasedonfeedbackcontrolscheduling,andasetofalgorithmsimplementingdifferentpoliciesandbehaviors.Ourapproachgivesarobustandcontrolledbehaviorofreal-timedatabases,evenfortransientoverloadsandwithinaccurateruntimeestimatesofthetransactions.Further,performanceexperimentsshowthattheproposedalgorithmsoutperformasetofbaselinealgorithmsthatusesfeedbackcontrol.

IndexTerms—Real-timeandembeddedsystems,real-timedataservices,imprecisecomputation,feedbackcontrol,modelingtechniques.

æ

1

INTRODUCTION

ATELY,

thedemandforreal-timedataserviceshas

increasedinanumberofapplicationssuchasmanu-facturing,Web-servers,ande-commerce.Further,theyarebecomingincreasinglysophisticatedintheirreal-timedataneeds[1],[2].Thedatanormallyspanfromlow-levelcontroldata,typicallyacquiredfromsensors,tohigh-levelmanagementandbusinessdata.Intheseapplications,itisdesirabletoprocessuserrequestswithintheirdeadlinesusingfreshdata.Indynamicsystems,suchasWebserversandsensornetworkswithnonuniformaccesspatterns,theworkloadofreal-timedatabases(RTDB)cannotbepreciselypredictedand,hence,theRTDBscanbecomeoverloaded.Asaresult,uncontrolleddeadlinemissesandfreshnessviolationsmayoccurduringthetransientoverloads.Toprovidereliableservicequality,weproposeaqualityofservice(QoS)sensitiveapproachthatguaranteesasetofrequirementsontheperformanceofthedatabase,eveninthepresenceofunpredictableworkloads.Further,forsomeapplications(e.g.,Webservice),itisdesirablethattheQoSdoesnotvarysignificantlyfromonetransactiontoanother.Here,itisemphasizedthattheindividualQoSneeds

L

requestedbytransactionsareenforcedand,hence,anydeviationsfromtheQoSneedsshouldbeuniformlydistributedamongtheclientstoensureQoSfairness.

Imprecisecomputationtechniques[3]havebeenintro-ducedtoallowflexibilityinoperationandtoprovidemeansforachievinggracefuldegradationduringtransientover-loads.Thesetechniquesmakeitpossibletotradeoffresourceneedsforthequalityofarequestedservice.Imprecisecomputationhasbeensuccessfullyappliedtoapplicationswheretimelinessisemphasized,butwhereacertaindegreeofimprecisioncanbetolerated[4],[5],[6],[7].Inourapproach,weemploythenotionofimprecisecomputationontransactionsaswellasdata,i.e.,weallowdataobjectstodeviate,toacertaindegree,fromtheircorrespondingvaluesintheexternalenvironment.Thiscombinedapproachofimprecisecomputationpresentsagreaterchallenge,butgivesbetterefficiencyinmanagingQoSandoverloadmanagement.

Inthispaper,wepresentaframeworkforspecificationandmanagementofQoSinimpreciseRTDBs.Thecon-tributionsofthispaperare

amodelforexpressingQoSrequirements,

anarchitecturebasedonfeedbackcontroltosatisfyagivenQoSspecification,

3.anewschedulingalgorithmthatenhancesQoS

fairness,and

4.amodelofthecontrolledsystemthatisusedto

synthesizefeedbackcontrollers.

Tothebestofourknowledge,thisisthefirstpaperonQoSmanagementofRTDBsusingimprecisecomputationsandfeedbackcontrol.

StartingwiththeQoSspecification,theexpressivepowerofourQoSspecificationmodelallowsadatabaseoperator

PublishedbytheIEEEComputerSociety

.M.AmirijooiswiththeDepartmentofComputerandInformationScience,

¨pingUniversity,S-58183Linko¨ping,Sweden.Linko

E-mail:meham@ida.liu.se.

.J.HanssoniswiththeSoftwareEngineeringInstitute,CarnegieMellonUniversity,Pittsburgh,PA15213-3890.E-mail:hansson@sei.cmu.edu..S.H.SoniswiththeDepartmentofComputerScience,SchoolofEngineeringandAppliedScience,UniversityofVirginia,151Engineer’sWay,POBox400740,Charlottesville,VA22904-4740.E-mail:son@virginia.edu.Manuscriptreceived2Apr.2004;revised29Apr.2005;accepted6July2005;publishedonline20Jan.2006.

Forinformationonobtainingreprintsofthisarticle,pleasesende-mailto:tc@,andreferenceIEEECSLogNumberTC-0112-0404.

1536-1233/06/$20.00ß2006IEEE

1.2.

Abstract—Real-time applications such as e-commerce, flight control, chemical and nuclear control, and telecommunication are becoming increasingly sophisticated in their data needs, resulting in greater demands for real-time data services that are provided

AMIRIJOOETAL.:SPECIFICATIONANDMANAGEMENTOFQOSINREAL-TIMEDATABASESSUPPORTINGIMPRECISECOMPUTATIONS305

tospecifynotonlythedesiredsteady-stateperformance,representingthenominalsystemoperation,butalsothetransient-stateperformancedescribingtheworst-casesys-temperformanceandsystemadaptabilityinthefaceofunexpectedfailuresorloadvariation.Continuingwiththesecondcontribution,wenoticethatthemainchallengewithmanagingQoSsuchthatthegivenspecificationissatisfiedistheunpredictabilityofworkloadintermsofunknownarrivalpatternsandinaccurateexecutiontimeestimates.Traditionalapproachesforprovidingperformanceguaran-tees[8]relyonknownworst-caseconditions,e.g.,worst-caseexecutiontimesandworst-casearrivalpatternsoftasks;ingfeedbackcontrolhasbeenshowntobeveryeffectiveforalarge …… 此处隐藏：6870字，全部文档内容请下载后查看。喜欢就下载吧 ……