epra 20 Arton pan Tgh zeny Transient Behavior of the Kendall Birth-Death Process—Applications to Capacity Expansion for Special Services By 8. N. NUGHO (neenuscrpt reid October 16, 1979) In this paper we derive explicit expressions for the transient stale probabilities of the Kendall birthdeath process, with and scithout ‘immigration, for any intial condition. We then propose this process ‘a8 a model for special serices point-to-point demand, ix which the ‘births represent ciruit “connects” and the deaths represent “discon rect." This choice of mite is based on intuitive arguments and on (he fact that the madel can represent the growth and twmnover characteristics of special sercices demand. Thus, the mode! provides ‘a means by which special services demand, sith ite inherent wer. tainty, may be approximately represented in various facility network ‘studies, 1 obtain, at the very least, useful qualitative reels, In articular, we evaluate the probability of a held order (ie, the ‘Probability hat a service request is held for lack of spare facies) teith Blocked Customers Held (Ron) as the quewe dieeipline. We also ‘op the model to capacity ezpaninn problems, introduce the con: ‘cept of margin, the extra eqpactty needed 19 meet the demand within 4 given helt-arder probabil, and examine its sensitivity with re- "pect to growth, tumover (or churn), and system size, We find that ‘Geeregating small demands ino a single larger demand produces ‘significant reduction of the margin, because of improved statistical properties, 1. iwrROBUCTION In this article, the tansiant behavior of Une Kendall birth-deach process" with immigration is examined, and aome applications of the ‘oasTig Kent eth presen inch nein ten opti ss process lo capacity expansion problems are discussed. The choice of Ihc process was motivated by the search for a rode for special fervices point-to-point cireult demand, 8 model which would be used ts a tool for determining facility network cireut routing strategien Special eervices demand ganeraly consis of demand for full-time dedicated vrewits (og, foreign exchange lines, wars line, deta lines), ts opposed to the measage-taffic offered load which consists of de- fund for the use of common fucilities for a velatively short period of time, Thusy the aystem examined is characterized by the stochastic process 0) with realizations (stats) n= 0,1, -->9o% where might fefer to the number of working eteuits or ome other facility, rather ‘han to the number of busy trunks, a in the message-tratfie case, By ‘efiniton, the bireh-death proce allows transions from some sale hhton + Lvin a birth (cir connect), or to n 1 via a death (cireull isconmnect). ‘The transition rates are‘, for the biths and uy for che ‘deaths, boll of hich are chosen proportional to 1 forthe fllowing Tei clear, for special sorviw, chat the rate of daconneets, po is state dependent. There sre n fact, indications that a i « monoton ‘cally increasing funetion of n.‘The simplest such function ism which implies thatthe probability of disconnects is proportional to the size fof thesystem. With this choice for Use deeth rato, a rember of possible ‘hoices exit fo the birch rae: Choosing it to be w constant eauses che tenn namber of ciccuits to saturate in time, while choosing it to be propotcional ton cares the mean to grow or decline exponentially Since spevial services are presently characterized by significant net frowth, it woud seem that m pliwible modal for special services ‘Semand sa bith and death proces in which bol the heh and death ‘ates are proportional to the sate ‘One consequence, however of assuming hy = 70a thet ifthe process reaches the Hate n= Oat any time, by 4 teseaion of disconnect, it rll stay there forever, sine the birth rate i zero. To eliminate this Characteristic, the concept of immigration may be intrdiced by taking Anamh + 8, where tthe Immigration factor. The cases wich and ‘without immigration wil be disused below. It must be emphasized that ic is not the incent of this paper to validate the model based on an examination of actual special wervices “dna, Such statistical data anni is important for a fnal assessment fof the accuracy of the moel and ie currently being undertaken, For the purposes of this paper, ic shall be assumed that a study of the ‘proposed model is justified, based on the inmitive arguments given Above and un the fact that the model captures the growth and turnover ‘characteristics of special services (se Section 5.1). The model provides {means by which special cervices demand, with it inherent uncer 8 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1981 tainty, may be approximately represented in various special services facility network studies, to obtain, atthe very least, useful qultaive recut ‘Since the situation of intaast is that of net growth, ita clear that statistical equilibrium does not exist and that iia the problem ofthe ‘transient aolutions ofthe Kolmogorov brth-death equations that is of prime importance, Much liverature exets on the eubject of transient lutions for bich-mnlsleath process and the ee in which the Uranilion rates are state indepenilent ie completely elved.”™ The cane in which A, and um are proparconal to the population is solved when ‘immigration i not included: The rule fora specific initial eondition, namely staring from the state x ~ I, ae derived in Refs. 4 and 10 and ‘the expression for the general initial condition are quoted in Raf. 10. For the nonsero immigration case, the form of the generaring function For the state probabilities fs kos,” at ema that explicit expres sons for the tate probabildes have not previously appeared in the literature. In this paper, these expressions are derived for any non- negative value of 8 Th special service, i an order for service is delayed because of lack of spare feclices, the order is aid to be held, Thus, inorder to study tapacity expansion problems, che probability of «held order is inte AAvoed, as wel a the concep” of mang, the extra expacity needed to rmeot the demand within x giver heldcorder probability. ‘This held- order probability ix similar but 1 identical to the tran time congestion ef the proves (see Appenilix B)- The «ew scipline fotlowed herein Blocked Cuntomer Held (nen), in which an arriving customer apends a tora time T (random variable) inthe sytem, aftr ‘which he departs rogurdless of whether he is waiting to be served (ie, his service oder has boen delayed) or is actually being served (Le, be thas hoen msignes a ere. ‘A furdamenal difference between this analysis and tletrafic muse be emphasized. Tia diflerence arses because of the respective time scale nthe 0 eases, Whereas the mean lifetime of 9 eall in afc {+= 1/h i ofthe order of fen minutes, the mean lifetime of a circuit in the process deserbed here is ofthe order of few yrs, I this fact, couple with the relatively Go growth of special werviees demand, ‘hat tnales ic impossible o even approximately teat the process in a Statistical equilum mode (pe growth) with a slomly varying enve- lopereprecensng the row, Thus, the transontaspoct of the problem. isto be concasted to the more conventional assumption, in eletrafc Cheory, that statistical equilibrium prevails (it must be mentioned, however, that some work has boon done concerning nonstationary telephone traffic with time-varying Poisson offered load, eg, Refs. 12 to 18). Te tnust be further noted that, although the modal is being APPLICATIONS OF SIRTH.OEATH PROCESS 59 proposed for special services demand, nevertheless, it may be applied, trith an appropriate choice of parameters A, fan to Ay process that behaves in similar manner. "The held-order probability having been defined and the concopt of margin introduced. questions concerning capacity expansion probledns fre addremsod. Capacity xpancion i a problem that has been eeudied by mang: In this paper, optimal eapacityexpansion policies are not sought; enl¥ very specialized anpecis of the problem are considered, For instance, the effects of aggregating demands into a larger single demand are examinod, and the minimum capacity increment which ‘would mect the demand within a apecified interval of time and within «given beld-order probability is determined, In addition, the relation ship between spare capacity and lead time is diacusaed (are urnmary ff result in Section TD. Some relevant work has been done by Freidenfelde“* in which the author computes frst-passage tes 10 various levels of demand using general bsth-death proces, and Aiseustes briefly ML-at-rliot problems. Work by Loss nd Whitt” studies the impact of both deterministic and stochastic models on Uutlization, ‘The authors use Browaian motion to model the stochastic ‘demand and follow a scheme siniar ta ours for determining che margin needed ata future time. "The organization ofthis paper is aa follows. Section II seta up the problem and gives a summary of rsults. Tho explicic solutions forthe fener cane ate derived in Secon TL, and this properties are exam ined in Section IV. In Section V, gevwth, turnover, and churn are defined, che concept of margin is introduced, and some of is applica: tions to capacity expansion problems are discussed. Finally, Setion ‘VT contains the conclusions |. BACKGROUND AND SUMMARY OF RESULTS. 121 General Birh-deeth equations ‘Consider a system deseribed hy «se of sates n=) 1,48, and ‘birth and desth process defined by a set of teanation rates (Mx pa) ‘Tho quantity Alia) + o(3) isthe probability of @ birch (death) in ‘the small inturval[,¢+ 6), given thatthe system isin state rat time The probability of more than one birth or death in [+8] i 18). ‘The probabilities a(t of finding the system in tate matte # matt satisfy the well-known infinite set of difference-differental equations (p. 464 of Het. 1) Phe Ha PAID + An Pa sl) wat Past Vor 420, PQ=0, moO} a) a pao ~ ot Re Reach ae 60. THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1981 1f the intial number of cirouita ia my che intial condition may be PaO By @ ‘whore By if the Kronecker dla "The particular birch-death process considered inthis paper are the eates in which the rursition zaves are proportional to the pop lation, n, wth oF without immigration **° The corresponding transi tion raten, defined for all nonnwgativeintogers,m, are er @ where 2, and faze nonnegative consinnts Tn the following sections, Zeeuls fr the cane with no Immigration may be easily obtained by setting, 12.2 Meen and vance {thas been shown'* that the mean, m(e, and che variance, o(), of ‘processes such as thowe deseribed hy eqs (1) apd (2) may be ebtained tvichout solving explicitly for Use 0). ‘The resulting expressions, {atiafying nitil eonition 2), may’ be easly found vo be (i) Case A mit= (ws « oe) = mt Baie = ht wet a 6 emer ” 2 so rope ee ir APPLICATIONS OF SIRTHLOEATH PROCESS 61 and (;)-teopeeomen © "This definition ofthe binomial coeficient is valid for any real number ‘rand any positive inter m (xp. 50 of Rf. 1) For m = 0, one defines (Gy = 1, and for negative integers m, one define (5) = 0. The symbol {f) ie not used ifm ie net an integer. Denoting » = A, where »fsany ‘ponnegacive rel number, the slations derived in this paper are (Caso #u cunmany "3" (") (" anton (A Dhit metro, a9) fay ify + =U a PA = Ly FN, Po = (money a on fa mata a (10) and (11) with no immigration (r= 0} are identical co of Re. 10} equa the results quoted by Bally [gs (8 24 Applicstion to capacity expansion In Section V, margin ia defined asthe capacity which n in excees of the mean lo matt certain service roquirements, and the proent marzin is delined ar che ratio ofthe margin to the mean in peveent. The flloring ies summary of the main results (i) By aggregating demands less percent margin is nooded than in tha nonageregaved case, This effect is expecially significant for seall demand, (G2) Given w minimum desired time, 7; botween successive expan- sions a procedure is establiahed for determining the minum eapacty increment which would mest the given service requirement Gi) Given a lead time,» bstoreen the moment facies are ordered and the time they are available for us, a prowdure is established for 22 THE BELL SYSTEM TECHNICAL JOURNAL JANUARY 1081 Aelermining the threshold value of the remaining epare coreeponding ‘athe tine at which new facilities should be ordered. (Ge) By introducing immigration, the sboorbing zero state is elim ‘ated and the percene margin needed to meet the eurvce requirements is reduce for moderavely lnrge to large times (of the order of two years, for more forthe particular values examined} 1, DERIVATION OF THE STATE PROBABILITIES ‘The approach followed (o wl the at of equations in (1) i the generating function technique" Tn Ref. 10, sdiferential equation for the generating function, Fs), defined below, is enablished and its rolulion i derived. "The resulta are quoted in Section 8.1. Three well Jmnown idenctien are given in Section 42 and are then used in Section 4.8 to derive explicie expressions for the state probabilicies. The pro ‘cedure flloweal in Berton 23s lo Wentiy Pl, €} a8 the generating function for convolution of nwo Funetions, ‘8.1. The generating function "The generating function, Fi, is vlated to the sate probabilities ‘through the fllowing exprerion Fin = 3 s'Pate oa) “The differential equation for F(, 0, gan ine. (269) of Ref. 10 with O88 ag) AFUE 3 TO ana) = 818 ~ F 0, as woe in) ~~e~ 90— ‘The wins igonncon ae [_4_y (hams (ea) les) Ati 08) (a) Ge) Fist APPUCATIONS OF BINTH-DEATH PROCESS 62 where a) 413) ‘The above solutions may be verified by direct substitution, Equation (46) agrees with og, (671) of Raf, 10 lo, (17) with =O agro wich 99. (862) of Ret. 10. In Section 1.8, use wil be made of the three following well-known identities 3.2.1 Binomial iontty or any a and and for any nonnegative intagor nthe following ideotity holds (p.51, Re. 1: (20) 3.2.2 Negative binomial ent For any a and f auch that [8/2] < 1 and for any real number the fullowing Wentity holds (seo pp. 51 and 269 of Tet.) co-ar'= E car(Z)ra ‘fri strictly postive, identity (12.4) on p. 68 of Hef. 1 may be used to write Coes (ane cae ey 3.2. Generating function for a convolution Let Fi(s) and Fis} be the generating functions for the sequences (64 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1981 (PE nnes+ and (PR acon ropectivay, Fin 3 sP2, Be) “The fonction F(s) = F(s)Fe(s) i then the generating function for (Pujeces ss the convolution of PS! and P2,and may be writen cr Be Fo) - 3 e's 23) where Pr Saveee $ one ‘The proof of this theorem is elementary (eg, see Chapter 11 of Ret, ‘Note: Thie theorem applies to arbitesry sequences {Pi} and {P2") (not necessarily probubility distributions) as lang as cheit respective -enerating functions exis. Thus, th serits in es (22) must converge. For the purpose of this theorer, however, is assumed that Fs) and Fis) do exist. 3.3 Detvation of expo axpreasions "The penerating function a eg (16! may be semaitzon as fllom: Fig, t= 6, 1818.0, om where File) ad beso", Fla (0H ast fa) mete >o Applying identity (20, it may be seen that #1, tis the generating function for binomial type function, Pose § (moreno = Brey, (25) APPLICATIONS OF BIRTH-DEATH PROCESS 65 where paw (Se if men, 0 if mon 29 1a similar manner, may’ be seen frown dency (21) that Fs is the generating funetion for x neyatve binomial type fanetion, en where {may be shown tha | ca «<1 fr all values of ¢ = 0,05 9 1, and Aya 0. Th, entity (21) applies in all che relevant casen Te mow flows fone, (2) tae Fy) the generating function of the convolution pale = F PPMP LAD ME [een] [eras Near ‘where the upper liv on ths sum avisgs from the eapdition ma for PEC establish hy e281 TRearranging one obtain yay I) rm he ta band ef a a em. sh {ore lr 10) vlan mera For this cass, Pls, 1) = 1. From the definition in eq (14), it ie then (66 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1981