Worst Case Analysis of Batch Arrivals with the Increasing Convex Ordering

Jean - Michel Fourneau

Description

Niveau: Supérieur, Doctorat, Bac+8
Worst Case Analysis of Batch Arrivals with the Increasing Convex Ordering ? Ana Busˇic(1), Jean-Michel Fourneau(1), and Nihal Pekergin(1,2) 1 PRiSM, Universite de Versailles Saint-Quentin-en-Yvelines, 45, Av. des Etats-Unis, 78035 Versailles, France 2 Centre Marin Mersenne, Universite Paris 1, 75013 Paris, France Abstract. We consider a finite buffer queue with one deterministic server fed by packets arriving in batches. We assume that we are not able to fully describe the batch distribution: only the maximal size and the average number of packets are supposed known. Indeed, these two quantities are simple to measure in a real system. We additionally allow the batch distribution to be state dependent. We analyze the worst case distribution of the queue length and the expectation of lost packets per slot. We show that the increasing convex ordering provides tight bounds for such a system. 1 Introduction In the case when we do not have complete information but some qualitative and quantitative information, a quite natural approach in many fields of ap- plied probability consists in finding an extremal distribution. For instance, in reliability modelling, one can compute the worst case Increasing Failure Rate distribution knowing the first moment (for the definitions and method see Bar- low and Proschan [2, p.

• stochastic matrix


• batch arrivals


• increasing convex


• vectors


• bounding icx


• monotone markov chain


• universite de paris


• icx


• strong stochastic

Sujets

• Fourneau
• United States
• Marin Mersenne
• Stochastic matrix
• Université de Paris

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 12
• Langue: English

Extrait

WorstCaseAnalysisofBatchArrivalswiththe IncreasingConvexOrdering ? AnaBusˇic´ (1) ,Jean-MichelFourneau (1) ,andNihalPekergin (1,2) 1 PRiSM,Universite´deVersaillesSaint-Quentin-en-Yvelines, 45,Av.desEtats-Unis,78035Versailles,France 2 CentreMarinMersenne,Universite´Paris1,75013Paris,France Abstract. Weconsiderafinitebufferqueuewithonedeterministic serverfedbypacketsarrivinginbatches.Weassumethatwearenot abletofullydescribethebatchdistribution:onlythemaximalsizeand theaveragenumberofpacketsaresupposedknown.Indeed,thesetwo quantitiesaresimpletomeasureinarealsystem.Weadditionallyallow thebatchdistributiontobestatedependent.Weanalyzetheworstcase distributionofthequeuelengthandtheexpectationoflostpacketsper slot.Weshowthattheincreasingconvexorderingprovidestightbounds forsuchasystem. 1Introduction Inthecasewhenwedonothavecompleteinformationbutsomequalitative andquantitativeinformation,aquitenaturalapproachinmanyfieldsofap- pliedprobabilityconsistsinfindinganextremaldistribution.Forinstance,in reliabilitymodelling,onecancomputetheworstcaseIncreasingFailureRate distributionknowingthefirstmoment(forthedefinitionsandmethodseeBar- lowandProschan[2,p.113]). InPerformanceEvaluationsuchamethodhasreceivedlessattention.The majorexceptionarethe( max, +)linearequationswhichnaturallyarisewhen onemodelsStochasticEventGraphs,asubsetofPetriNets(seethebookby Baccellietal.[1]foraconsiderablesurveyonthesetopics).Mostoftheresults obtainedinthisbookcanbegeneralizedtomodelsexhibitingstochasticlinear recurrenceequationsinsomesemirings:forinstance(min,max)semiringor (min,+)semiring.Theseresultsarebasedonthepropertiesofthesemirings: whenweconsidermorecomplexalgebraicstructuresmostresultsdonotapply anymore. AcompletelydifferentideawasrecentlyproposedbyP.Buchholz[5].The mainassumptionisthatthemodellersdonotknowtherealtransitionproba- bilities.Thus,onewantstomodelasystembyafamilyofMarkovchainswhere thetransitionprobabilitiesbelongtoaninterval.Onehastoderivetheworst case(orthebestcase)forallthematricesintheset.Thetheoreticalarguments ? ThisworkwassupportedbyprojectSure-PathsfromACIandtheFrench“pro- grammeblanc”projectSMS.