Specification and management of QoS in real-time databases s(2)

Imprecisionatusertransactionlevelcanbeexpressedintermsofcertainty,accuracy,andspecificity[4].Certaintyreferstotheprobabilityofaresultbeingcorrect,accuracyreferstothedegreeofaccuracyofavaluereturnedbyanalgorithm(typicallythroughaboundonthedifferencefromtheexactsolution),andspecificityreflectsthelevelofdetailoftheresult.Forexample,iffiltersareusedincontrolloops,greateraccuracyisachieved.Specificityisusedtodefineusertransactionimprecisioninthecontextofimagecodingordecoding.Theimprecisionoftheresultofausertransactionincreasesastheresourceavailablefortheusertransactiondecreases.Forsimplicity,werefertotheimprecisionoftheresultsoftheusertransactionsasqualityoftransaction(QoT)ually,systemdevelopersknowhowmuchdataimprecisionanapplicationcantoleratesuchthattheendresultiswithinacceptablelimits.Therefore,weassumethatsufficientlyprecisedatavaluesstoredinthedatabaseareregardedashavingnoeffectontheresultofatransaction.Hence,wemodelQoTandQoDasorthogonalentities.SystemdeveloperscanthenfocusonfindingappropriateprecisionrequirementsandavoidmodelingQoTasfunc-tionsofQoD.ThissignificantlyreducesthecomplexityoftheQoSspecificationprocess.

QoTismanipulatedbyadjustingtheadmittedusertransactionloadandtheadmittedupdatetransactionload.TheCPUresourceallocatedforeachusertransactiondecreasesasthenumberofadmittedusertransactionsandthenumberadmittedupdatetransactionsincrease,resultinginadecreaseinQoT.Theupdatetransactionloadisreducedbydiscardingupdatetransactionsaccordingtoanupperboundforthedataerrorgivenbythemaximumdataerror,denotedmde.Note,discardingupdatetransac-tionsreducesQoD,however,weassumethatQoTisnotaffectedbyQoDastheyaremodeledtobeorthogonal.An

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

306updatetransactionTjisdiscardedifthedataerrorofthedataobjectditobeupdatedbyTjislessthanorequaltomde(i.e.,dei mde).Ifmdeincreases,moreupdatetransactionsarediscarded,degradingtheQoD.Thisresultsinmoreresourcesavailableforusertransactionsand,hence,anincreaseinQoT.Similarly,ifmdedecreases,fewerupdatetransactionsarediscarded,resultinginagreaterQoDand,consequently,alowerQoT.Thegoalofourworkconsistsoftwoparts.Wewanttoderive:1)algorithmsforadjustingdataerrorusingmdesuchthatQoDandQoTsatisfyagivenQoSspecificationandthedeviationinimprecisionofusertransactionresultsisminimized,i.e.,QoSfairnessismaximized,and2)afeedbacklooparchitecturethatishighlyreactiveandadaptivetochangestoworkloadcharacteristics.Thesecondpartimplies,asarguedinSection1,thatweneedtofindaccuratemodelsofthecontrolledsystemtoprovideefficientQoSadaptabilityandperformancereliabilityeveninthepresenceofunpredictableworkload.

3DATA

AND

TRANSACTIONMODEL

WeconsideramainmemorydatabasemodelwherethereisoneCPUasthemainprocessingelement.Mainmemorydatabaseshavebeenincreasinglyappliedtoreal-timedatamanagementduetotheirrelativelyhighperformance,decreasingmainmemorycost,fastresponsetime(sinceI/Ooverheadisdecreased),andtheemergenceofembeddedsystemslackingdisks[15],[16].Inourdatamodel,dataobjectscanbeclassifiedintotwoclasses,temporalandnontemporal[17].Fortemporaldata,weonlyconsiderbasedata,i.e.,datathatholdtheviewoftherealworldandareupdatedbysensors.Abasedataobjectdiisconsideredtemporallyinconsistentorstaleifthecurrenttimeislaterthanthetimestampofdifollowedbythelengthoftheabsolutevalidityintervalofdi(denotedavii),i.e.,currenttime>timestampiþavii.Foradataobjectdi,letdataerrordei¼Èðcvi;viÞbeanonnegativefunctionofthecurrentvaluecviofdiandthevalueviofthelatestarrivedtransactionthatupdateddiorthatwastoupdatedibutwasdiscarded.RememberanupdatetransactionmaybediscardedifitsupdatevalueiscloseenoughtothevaluestoredintheRTDB.OurapproachdoesnothaveanyrestrictionsonthestructureofÈ.Forexample,itmaybedefinedastheabsolutedeviationbetweencviandvi,i.e.,dei¼jcviÀvij,ortherelativedeviationasgivenby

dei¼jcviÀvij

ertransactionsarriveaperiodicallyandmayreadtemporalandread/erandupdatetransactions(Ti)arecomposedofonemandatorysubtransactionmiandjOij!0optionalsubtransactionsoi;j,whereoi;jisthejthoptionalsubtransactionofTi.Fortheremainderofthepaper,welettidenoteasubtransactionofTi.Asupdatesdonotusecomplexlogicalornumericaloperations,weassumethateachupdatetransactionconsistsonlyofasinglemandatorysubtransaction,i.e.,jOij¼0.

Asmentionedearlier,thereareseveralwaysofim-plementingimprecisecomputations,e.g.,multipleversions,

IEEETRANSACTIONSONCOMPUTERS,VOL.55,NO.3,MARCH2006

useofsievefunctions,andthemilestoneapproach[3].ThefocusofthispaperisnotonhowtoapplydifferentimprecisecomputationtechniquesinthecontextofRTDBssincethisareahasalreadybeenexplored,asshowninSection6.Previousworkindicatesthatiterativeandrecursivealgorithms,generatingmonotonicallyimprovinganswers,canbeefficientlyusedtosolveproblemsinawideclassofapplications,suchas,numericalalgorithms,e.g.,Newton’smethodandFFT[18],graphalgorithms[4],andalsoqueryprocessing[6],[7].Iterativeandrecursivealgorithmscaneasilybemodeledusingthemilestoneapproach,wherethekfirstiterationsorrecursionscorrespondtothemandatorypartandtheremainderaregivenbytheoptionalpart.Forthisreason,weusethemilestoneapproach[3]totransactionimpreciseness.Thus,wedividetransactionsintosubtransactionsaccordingtomilestones.Amandatorysubtransactioniscompletedwhenitiscompletedinatraditionalsense.Themandatorysubtransactiongivesanacceptableresultandshouldbecomputedtocompletionbeforethetransactiondeadline.Theoptionalsubtransactionsmaybeprocessedifthereisenoughtimeorresourcesavailable.WhileitisassumedthatallsubtransactionsofatransactionTiarriveatthesametime,thefirstoptionalsubtransaction(ifany)oi;1becomesreadyforexecutionwhenthemandatorysubtransactionmiiscompleted.Ingeneral,anoptionalsubtransactionoi;jbecomesreadyforexecutionwhenoi;jÀ1(where2 j jOij)completes.We …… 此处隐藏：6119字，全部文档内容请下载后查看。喜欢就下载吧 ……