A State-Dependent Approximation for the Generalized Engset Model

Publish in

Documents

7 views

Please download to get full document.

View again

of 3
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, DECEMBER 2009 1 A State-Dependent Approximation for the Generalized Engset Model Eric W. M. Wong, Senior Member, IEEE, Andrew Zalesky, and Moshe Zukerman, Fellow, IEEE Abstract—The well-known Engset model has been widely used and studied. In this paper, we propose a new state dependent approximation for a special case of the generalized Engset model that considers packet/burst dumping. We also correct here several errors in [7] which considered th
Tags
Transcript
  IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, DECEMBER 2009 1 A State-Dependent Approximation for the Generalized Engset Model Eric W. M. Wong, Senior Member, IEEE  , Andrew Zalesky, and Moshe Zukerman, Fellow, IEEE   Abstract —The well-known Engset model has been widely usedand studied. In this paper, we propose a new state dependentapproximation for a special case of the generalized Engset modelthat considers packet/burst dumping. We also correct here severalerrors in [7] which considered the same model. Numerical resultsover a wide range of parameters demonstrate the superiority of the new approximation over previous ones.  Index Terms —Blocking probability, Engset formula, OBS,bufferless optical networks. I. I NTRODUCTION I N this paper, we consider one of Cohen’s generalizationsof the Engset model [2], [4] in which the time beforea source generates a new call is dependent on the successof the previous call. The concept of a call , which wasrelevant to telephony, was often used in classical work on theEngset model. In the context of modern networking researchit represents packets or bursts. In this paper, we will use calls,packets or bursts, interchangeably. In our modeling, they allrefer to jobs offered to a service system.This generalization is applicable to optical burst (or packet)switching [1], [3], [8], in which a blocked burst is dumped,and until the dumping is completed, a source cannot generate anew burst. The salient feature that distinguishes such a specialcase from the traditional Engset model is that a source mustcompletely transmit (i.e. dump) a blocked burst before a newburst can be generated. In contrast, the Engset model assumesa new burst can be generated immediately after a blockingevent which results in blocking probability overestimation.Therefore, it was proposed in [5], [6], [7] to increase thesource’s off-time to capture the burst dumping effect.In this paper, for a given source, the mean effective off-time (MEOT) refers to the mean time period between the endof transmission of a successful burst and the commencementof transmission of the next successful one. This period mayincorporate the dumping of blocked bursts. We consider hereMEOT for each source to be dependent on the number of busy channels, and demonstrate that this leads to an approxi-mation which is consistently more accurate than all previousproposals. In addition, we correct several errors made in [7]. Manuscript received May 22, 2009. The associate editor coordinating thereview of this letter and approving it for publication was M. Ma.E. W. M. Wong and M. Zukerman are with the Department of ElectronicEngineering, City University of Hong Kong, Hong Kong SAR, China (e-mail:ewong@ee.cityu.edu.hk; m.zu@cityu.edu.hk).A. Zalesky is with the University of Melbourne, Victoria 3010, Australia(e-mail: azalesky@unimelb.edu.au).The work described in this paper was supported by a grant from CityUniversity of Hong Kong (Project No. 7002478).Digital Object Identi fi er 10.1109/LCOMM.2009.091115 II. T HE M ODEL We consider the loss model of [7], [8] involving   sourcesthat offer calls/packets/bursts to   channels/servers. Both   and   are assumed to be fi nite integers. We assume the case  >   , but we do not consider the case  >>   , whichdegenerates to the Erlang system as   approaches in fi nity. Onthe other hand, if    ≤   , the call-congestion is equal to zero.Neither the case  >>   , nor the case   ≤   , is of interestto us here. We assume that the packet transmission or dumpingtimes are independent and exponentially distributed with mean 1 / . At any point in time, any of the   sources is eitheractive, idle or dumping. During an active period, a sourcewill transmit a successful packet. A source cannot generate anew packet during either an active or a dumping period. Theend of an active or dumping period is always a beginning of an idle period. The length of an idle period is assumed to beindependent and exponentially distributed with mean 1 / . Assoon as an idle period ends, the source generates a new packet.The new packet is blocked if all   channels are already busy,which results in a dumping period. Otherwise, the new packetis successful, which results in an active period for that source.III. A S TATE -D EPENDENT A PPROXIMATION The aim here is to fi nd the MEOT for each source which isdependent on the number of busy servers such that a single di-mensional Markov chain can be used to accurately predict theblocking probability. Having an accurate approximation basedon a single dimension is important because exact results forthe generalized Engset relies on a 2-dimensional Markov chainthat are not scalable for large  and   . Note that althoughsigni fi cant computational improvement can be achieved usingMatrix methods [1], they are still not as scalable as a singledimensional solution.All the approximations considered in [7] were based onlengthening the off-period from 1 / to  to compensatefor the time that packets or bursts are dumped immediatelyfollowing a blocking event. However, they all do not considerthe fact that during periods of higher carried traf  fi c load thereare more blocking and thus more dumping, so the MEOTs arelonger. Therefore, we propose here to achieve higher accuracyby considering the MEOT to be state-dependent. To this end,we de fi ne   to be the MEOT in state  , namely when thereare  busy servers,  = 0 , 1 , 2 , ...,   .Note that in the traditional Engset model, bursts arrive atrate (   −  ) /  in state  , where   =  = 1 / for all  . The traditional model is therefore typically considered tobe state-dependent but the MEOT (for each source) is state-independent. In our new model, we allow the MEOT to bedependent on system state  (i.e.   ∕ =  ). 1089-7798/09$25.00c ⃝ 2009 IEEE  2 IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, DECEMBER 2009 Let   be the probability of having  servers busy,  =0 , 1 , 2 , ...,   . The   and   values satisfy the followingsteady state equations.   +1 =   −   (  + 1)   , for  = 0 , 1 , 2 , ...,   − 1 , (1)where the   values are set to increase linearly with  asfollows   =1  +(  + 1) . (2)The choice of a linear relationship between   and the state  is made for simplicity. The constant  is obtained as follows.  +   =  ∑  =0 (   −  )     . (3)In the real system, an idle period of mean length 1 / isalways followed by a transmission/dumping period of meanlength 1 / . The true burst arrival rate per source is therefore 1 / ( 1 / + 1 / ) and is thus independent of the blockingprobability. The left hand-side of (3), which is given bymultiplying this expression by / , is the intended  offeredload in the real system.In (3), we equate the intended  offered load, namely theoffered load in the real system of the on-off sources (includingthe dumped packets/bursts) to the offered load in the model.Substituting (2) into (1) and (3) and together with thenormalization equation   =0   = 1 , we have   +2 equationsand   +2 unknowns (i.e.  and   where  = 0 , 1 , ...,   )which form a set of  fi xed point equations and can be solvedby the algorithm provided in the next section.The blocking probability is then derived by Π  = 1 − carried loadoffered load where carried load =   − 1  =0(   −  )      .In the remaining part of this section, we prove that a uniquesolution exists for the set of coupled fi xed-point equationsde fi ned by (1), (2) and (3) together with the normalizationequation. This solution is our new state-dependent approx-imation for call congestion. As we cannot guarantee thatthe successive substitution algorithm [5] converges to theunique solution, we provide a binary search algorithm tonumerically compute the unique solution for the set of  fi xed-point equations and we prove its convergence. Finally, in thenext section, we numerically compare the accuracy of our newstate dependent approximation with Syskis approximation andthe approximations in [5] and [7].  A. Existence and Uniqueness of the Fixed Point Solution By setting  =  in (2) and moving the left-hand side of (3) to the right, we de fi ne the function   (  ) =  ∑  =0 (   −  )   (  )   −  + , (4)where we have written   (  ) instead of    to emphasize that   is functionally dependent on  through (2). Our task is toprove   (  ) = 0 ,  ≥ 0 , has a unique solution. Algorithm 1 Calculate solution of    (  ) = 0 for an absoluteerror criterion of   1:  − ← 0 ,  + ←   Initial lower/upper bounds 2: while  + −  − >  do 3:  ← (  + +  − ) / 2 Halve the search interval 4: if    (  ) > 0 then 5:  − ←  Tighten lower bound 6: else 7:  + ←  Tighten upper bound 8: end if  9: end while 10: return  ← (  + +  − ) / 2  satis fi ed, thus return  To establish solution existence, we observe that   (  ) iscontinuous and changes sign at least once for  ≥ 0 . Thisis because for  = 0 ,   = 1 / and the system degeneratesto the Engset system and hence   (0) > 0 since in the Engsetsystem the offered load is larger than the intended  offered loadfor Π  > 0 . On the other hand, for  =    (   ) =  ∑  =0 (   −  )  1  +  +1     −  + , (5) <  ∑  =0    1  + 1     −  +   = 0 Therefore, a solution exists by the intermediate-value theorem.To establish solution uniqueness, suppose   (  1 ) =   (  2 ) =0 for  2 >  1 ≥ 0 . The mean-value theorem requires theexistence of an  satisfying   (  2 ) −   (  1 ) =   ′ (  )(  2 −  1 ) or   ′ (  ) = 0 , where  1 ≤  ≤  2 . This provides us witha contradiction because simple calculations reveal   ′ (  ) < 0 (the proof is provided in the Appendix). Therefore,  1 =  2 .  B. Binary Search Algorithm to Solve   (  ) = 0 This is the well known binary search algorithm. The onlyreason we present it here is to correct our errors in the samealgorithm introduced in [7]. Let  ∗ be the unique solutionof    (  ) = 0 . Due to the monotonicity of    (  ) , at eachiteration of Algorithm 1, if   <  ∗ , then   (  ) >   (  ∗ ) = 0 .Conversely, if   >  ∗ , then   (  ) <   (  ∗ ) = 0 . Consequently,  ∗ lies in the interval [  − , + ] at each iteration of Algorithm1. Furthermore, this interval halves at each iteration, therebyensuring  ∗ is sandwiched within an interval whose eventuallength does not exceed  . Thus, Algorithm 1 converges to aunique solution of    (  ) = 0 with error  .IV. N UMERICAL R ESULTS Figs. 1 and 2 show blocking probability versus normalizedtraf  fi c intensity  = ( /  )( / ) for   = 2 and   = 1 and for   = 6 and   = 3 , respectively. These fi guresdemonstrate that the new state-dependent (SD) approximationis consistently more accurate than all previous proposals. See[9] for further numerical results that demonstrate advantagesof the MEOT state-dependent approach.  WONG et al. : A STATE-DEPENDENT APPROXIMATION FOR THE GENERALIZED ENGSET MODEL 3 00.511.5200.050.10.150.20.250.30.350.40.45N = 2, K = 1Normalized Traffic Intensity, ρ    B   l  o  c   k   i  n  g   P  r  o   b  a   b   i   l   i   t  y Syski’s ApproxApprox [5]SD ApproxExact SolutionApprox [7] Fig. 1. Blocking probability versus normalized traf  fi c intensity  for   = 2 and   = 1 . 00.511.5200.050.10.150.20.250.30.35N = 6, K = 3Normalized Traffic Intensity, ρ    B   l  o  c   k   i  n  g   P  r  o   b  a   b   i   l   i   t  y Syski’s ApproxApprox [5]SD ApproxExact SolutionApprox [7] Fig. 2. Blocking probability versus normalized traf  fi c intensity  for   = 6 and   = 3 . V. C ORRECTIONS TO [7]In lines 5 and 7 in Algorithm 1 in the 3rd page of [7],the updated  − / + should be set to  instead of  Γ(  ) .This change ensures the algorithm is a true “Binary SearchAlgorithm” as claimed in [7]. It guarantees convergence ina bounded number of steps. We cannot prove (or disprove)convergence if this change is not made. Also, some of thevalues reported in reported in Table 1 of [7] are in error.Speci fi cally, all the rows in Table 1 listed as  = 0 . 9 actuallycorrespond to  = 0 . 8 . And the entire “New” column is inerror due to a programming bug. This resulted in incorrectconclusions reported in [7] about the superiority of the “New”approximation.VI. C ONCLUSION We have provided a new MEOT state-dependent approx-imation and corrected several errors in [7] for a versionof the generalized Engset model that considers packet/burstdumping. We have demonstrated numerically that the newapproximation is consistently more accurate than previousproposals.A PPENDIX : P ROOF OF   ′ (  ) < 0 Recall   =   (  ) = 1  +  +1  .   (  ) can be written as   (  ) =  ∑  =0 (   −  )     −  +   =(   −   )     +  ∑  =1   −  +   =(   −   )     +  ∑  =1   ∑  =     −  + . Proving   (  ) is decreasing in  or  means proving   =    is decreasing in   since   is increasing in  . Since   = ∏  =         where  = 0 , 1 , 2 , ...,   and   ≜ (  +1)   −  for  = 0 , 1 , 2 , ...,   − 1 or ≜ 1 /  for  =   ,we have  ∑  =    =   =  ∏  =        =0 ∏  =       =1 ∑  − 1  =0 ( ∏  =      ) ∑  =  ( ∏  =      )+ 1=1 ∑  − 1  =0 ( ∏  =      ) / ( ∏  =    ) ∑  =  ( ∏  =      ) / ( ∏  =    )+ 1=1 ∑  − 1  =0 ( ∏  =    )( ∏  − 1  =    ) ∑  =  ( ∏  =    ) (∏  − 1  =  1  ) + 1 where  = 1 , 2 , ...,   and ∏  − 1  =  1   ≜ 1 . Since   > 0 ,   − 1  =0 ∏  =    ∏  − 1  =     is increasing in   and   =  ∏  =    ∏  − 1  =  1    is decreasing in   ,and hence   =    is decreasing in   . Therefore,   (  ) isdecreasing in  or  .R EFERENCES[1] N. Akar and Y. Gunalay, “Stochastic analysis of  fi nite population buffer-less multiplexing in optical packet/burst switching systems,” IEICE Trans. Commun. , vol. E90-B, no. 2, pp. 342-345, 2007.[2] J. W. Cohen, “The generalized Engset formulae,” Philips Telecommun. Rev. , vol. 18, pp. 158-170, 1957.[3] H. Overby, “Performance modelling of optical packet switched networkswith the Engset traf  fi c model,” Optics Express , vol. 13, pp. 1685-1695,2005.[4] R. Syski, Introduction to Congestion Theory in Telephone Systems .North Holland, 1959.[5] H. L. Vu et al. , “Scalable performance evaluation of a hybrid opticalswitch,” J. Lightwave Technol. , vol. 23, pp. 2961-2973, Oct. 2005.[6] E. W. M. Wong and M. Zukerman, “Bandwidth and buffer tradeoffs inoptical packet switching,” J. Lightwave Technol. , vol. 24, no. 12, pp.4790-4798, Dec. 2006.[7] E. W. M. Wong, A. Zalesky, and M. Zukerman, “On generalizations of the Engset model,” IEEE Commun. Lett. , vol. 11, no. 4, pp. 360-362,Apr. 2007.[8] M. Zukerman, E. W. M. Wong, Z. Rosberg, G. M. Lee, and H. L. Vu,“On teletraf  fi c application to OBS,” IEEE Commun. Lett. , vol. 8, pp.116-118, Feb. 2004.[9] A. Zalesky, E. W. M. Wong, M. Zukerman, and H. L. Vu, “Engsetformula for bufferless OBS/OCS: when is and when isn’t lengthening theoff-time redundant?” Proc. IEEE GLOBECOM 2009 , to be published.
Related Search
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks