Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.19 No.2 pp.358-366
DOI : https://doi.org/10.7232/iems.2020.19.2.358

A Note on Approximations of Discrete-Time Queueing Systems with Their Continuous-Time Counterparts

Nam K. Kim, Won Seok Yang*, Mohan L. Chaudhry, Kilhwan Kim
Department of Industrial Engineering, Chonnam National University, Gwangju, Republic of Korea
Department of Business Administration, Hannam University, Daejeon, Republic of Korea
Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, Ontario, Canada
Department of Management Engineering, Sangmyung University, Cheonan, Chungnam, Republic of Korea
*Corresponding Author, E-mail: wonsyang@hnu.kr
July 12, 2019 November 19, 2019 April 6, 2020

ABSTRACT


In this paper, we discuss the performances of approximations of discrete-time queues with their continuous-time counterparts. Taking the discrete-time single-arrival Geo/G/1, batch-arrival GeoX/G/1, and tandem queues for examples, we present the absolute and relative errors resulting from such approximations and demonstrate that they can be quite vulnerable for a considerable range of parameter values. Therefore, special attention has to be paid to such approximations, and further sophisticated analysis needs to be carried out for more accurate evaluation of discrete-time queueing systems, taking their discrete-time characteristics into account.



초록


    1. INTRODUCTION

    For decades, queueing models have been widely applied to computers and communication systems and other related areas for their performance analyses and systems designs (Kleinrock, 1976;Walrand, 1991;Harchol-Balter, 2013). To deal with queueing problems arising in such systems, using the results of queueing analysis is more advantageous than simply projecting existing experiences or simulation results because it is computationally efficient and provides reasonable solutions (Stallings, 1998).

    Such queueing systems can be analyzed essentially as either continuous-time queueing models or discretetime ones. In continuous-time queueing models, the time axis is a continuous real-valued one. In discrete-time queueing models, on the other hand, the time axis is segmented into a sequence of equal intervals, called slots, and services of customers, such as transmissions of cells, packets, or messages are assumed to start and end only at the slot boundaries.

    Discrete-time queueing models have been known to be better capable of representing discrete characteristics of a variety of slotted digital communication systems and other related ones (Bruneel and Kim, 1993;Miyazawa and Takagi, 1994;Woodward, 1994;Alfa, 2016). Historically, however, continuous-time modeling has been paid much greater attention for analyzing such discrete-time systems, seemingly based on the following reasons.

    First, analysis of discrete-time queueing models appears to be more complex than those of their continuoustime counterparts, primarily due to the fact that several events can take place at the same time under the discretetime setting, whereas only a single event can take place at any time point under the continuous-time setting. As a result, it seems like that many researchers and practitioners, who are familiar with continuous-time queueing analysis, are not as much at ease with discrete-time counterparts.

    Second, theoretical analysis of many discrete-time queueing models runs pretty much parallel to their continuous- time counterparts. Moreover, it has been shown that theoretical results for certain discrete-time queueing models approach their continuous-time counterparts by taking the duration of a slot to be infinitesimal; see, e.g., p.35 of Takagi (1993) and Chaudhry and Goswami (2019), respectively, for such relations between batch-arrival GeoX/G/1 and MX/G/1 queues as well as between multiserver Geo/Geo/c and M/M/c queues. Besides, astonishing speed of current digital communication systems would take just a few milli- or even several micro-seconds to send a packet or a message, such that the slot duration is indeed very tiny. In view of this, one may want to jump to a conclusion that it should be reasonable to approximate a discrete-time queueing system having a tiny slot duration with its continuous-time counterpart.

    Third, some of the results are not even available for certain discrete-time queueing models, which are readily available for their continuous-time counterparts. Consider, for example, a discrete-time version of the Jackson network, in which n nodes of discrete-time single-server queues with geometric service times are connected to each other and customers may move from one node to another in an arbitrary order. While remarkably simple product-form results are available for the celebrated continuous- time Jackson network and its generalizations (Wolff, 1989), such results are not available under the discrete-time setting in general; only for some limited cases, product-form results are presented (Daduna, 2011). In such a case, where useful discrete-time results are not available, one may find it quite appealing to approximate discrete-time queueing systems with their continuoustime counterparts, presuming that the latter can serve as a good approximation for the former.

    However, such an approximation, in fact, cannot be as accurate as one desires. In this paper, we explicitly discuss what its performance would be like over the ranges of the parameter values, if one indeed carries out such an approximation because of the three reasons mentioned above, (i.e., unfamiliarity with the discrete-time queuing models, mistaken presumption on numerical closeness between the discrete- and continuous-time models, unavailability of the desired discrete-time results,) or even otherwise. To do this, we consider a kind of system approximation, in which primary mean performance measures, such as the mean waiting time and the mean queue length, of the discrete-time systems are approximated by using those of the corresponding continuoustime systems with appropriate parameter adjustment. Considering the discrete-time single-arrival Geo/G/1, batch-arrival GeoX/G/1, and tandem queues for examples, we present the absolute and relative errors resulting from such approximations, discuss how those errors originate, and demonstrate how they vary according to the changes of the parameter values, so as to see when the approximations work or fail.

    In the approximations along these lines, note that the parameters of the discrete-time systems, such as the slot duration ( Δ ) and the probability (λD ) that a customer arrives at a slot, are not controllable variables but predetermined constants (e.g., Δ =10 millisecond) given by the discrete-time system to be approximated; hence, one cannot choose Δ and λD to be certain desired values. In the approximations in the opposite direction, on the other hand, i.e., approximations of the continuous-time systems by use of the results from their discrete-time counterparts, those discrete-time parameters can be controlled to be any (tiny) values, so that one can make use of the theoretical limiting results mentioned above. We do not consider such approximations in this direction in the paper.

    This paper is organized as follows. We begin with a preliminary approximation in Section 2 to see what would indeed happen if the Bernoulli process is approximated with its Poisson counterpart. Then, in Section 3, we consider an approximation of the discrete-time single-arrival Geo/G/1 queue with the continuous-time M/G/1 counterpart and discuss the errors brought about by this approximation. Along these lines, in Section 4, we discuss how the errors become when the batch-arrival GeoX/G/1 queue is approximated with the MX/G/1 counterpart. In Section 5, we demonstrate the errors that are brought about when a certain discrete tandem network is approximated with its continuous-time counterpart. We conclude the paper in Section 6.

    Throughout the paper, we assume for the discretetime queueing models the arrivals first policy or the late arrival system (LAS); for details, see, e.g., Takagi (1993). All the time-average results (observed at an arbitrary point in the middle of a slot) as well as the waiting time of a customer (discussed in this paper) are, however, invariant even if we assume a different assumption, the departure first policy or the Early arrival system (for their details and further discussions along these lines, see p.38 of Takagi (1993) and Remark 10 of Kim et al. (2004)).

    2. APPROXIMATING THE BERNOULLI PROCESS WITH ITS POISSON COUNTERPART

    In this section, we preliminarily discuss what would happen if the Bernoulli (arrival) process having parameter λD is approximated with its continuous-time counterpart, or Poisson (arrival) process with parameter λC. (Throughout the paper, we use subscripts C and D to represent respective continuous- and discrete-time quantities; we don’t use subscripts C nor D when a quantity represents both the continuous- and discrete-time ones; for example, E[W] represents the mean waiting time for both continuous- time E[WC] and discrete-time E[WD] ). While λD and Δ are predetermined constants given by the discrete- time system, λC needs to be determined for this approximation: one of the reasonable ways, which we use in this paper, is to use λD / Δ in place of λC.

    Note that the interarrival times of the Bernoulli and Poisson processes, denoted by random variables XD and XC, respectively, have i.i.d. (independent and identically distributed) geometric and exponential distributions (Takagi, 1991, 1993); hence, approximating a Bernoulli arrival process with its Poisson counterpart can be considered as approximating the corresponding geometric interarrival distribution by its exponential counterpart. Now, we approximate the Bernoulli arrival process having λD and Δ with the corresponding Poisson process having λC =λD / Δ ; as a result, it turns out that the tail distribution of XD is approximated with the corresponding tail distribution of XC / Δ as follows:

    P ( X D > n ) P ( X C / Δ > n ) = P ( X C > n Δ ) = e ( λ D / Δ ) n Δ = ( e λ D ) n
    (1)

    for n = 0, 1, 2, ⋯, note here that the exponential random variable XC, expressed in terms of time, is divided by Δ in order to be expressed in terms of slots to approximate XD.

    Note that the right-most side of (1) does not depend on Δ , so no matter how small Δ is predetermined by the given discrete-time system, it is not relevant. In this approximation, only for such cases in which λD is very tiny (such that e λ D 1 λ D ), it is close to the exact tail probability: P ( X D > n ) = ( 1 λ D ) n . Note also that this approximation always overestimates the exact tail probabilities.

    Table 1 gives absolute errors and relative errors (i.e., the absolute errors divided by the exact calculations) for P(X > n) in cases of λD = 0.1 and 0.001. From this, it can be seen that the geometric tail distribution is better approximated with its exponential counterpart in case of λD =0.001. In fact, it is well known that a Poisson arrival process can be nicely approximated with its Bernoulli counterpart by taking λD and Δ to be sufficiently small. Note, however, that λD (as well as Δ ) in the approximation above is not a controllable variable but a predetermined constant given by the discrete-time system to be approximated.

    3. APPROXIMATING THE GEO/G/1 QUEUE WITH ITS M/G/1 COUNTERPART

    In this section, we discuss what would happen if the discrete-time Geo/G/1 system with a Bernoulli arrival process having parameter λD and a service time having a discrete positive random variable SD is approximated by using its continuous-time M/G/1 counterpart with a Poisson arrival process having rate λC and a service time having a random variable SC.

    For the continuous-time M/G/1 and the discrete-time Geo/G/1 queues, Table 2 below gives the performance measures of primary interest, i.e., the mean number of customers waiting in the queue (excluding the one in service), denoted by E[N], and the mean time (or the mean number of slots in the discrete-time case) a customer spends waiting in the queue (excluding her time in service), denoted by E[W]. For their derivation, see, e.g., Takagi (1991, 1993).

    In Table 2, note that the traffic intensities are given by ρ C = λ C E [ S C ] < 1 and ρ D = λ D E [ S D ] < 1 . In addition, it can be seen that E[ND] and E[WD] for the discretetime Geo/G/1 queue have the terms λ D ρ D / 2 ( 1 ρ D ) and ρ D / 2 ( 1 ρ D ) , respectively, that do not correspond to E[NC] and E[WC] for its continuous-time M/G/1 counterpart.

    For an approximation of the Geo/G/1 queue with the corresponding M/G/1 queue, one of the reasonable ways, which we use in this paper, is to approximate the Bernoulli arrival process having parameter λD with the corresponding Poisson process having rate λC = λD / Δ and to use SD ⋅Δ in place of SC (To use discrete random variable SD ⋅Δ in place of SC, in fact, does not invite errors by itself since the service time under the M/G/1 setting, in general, is not confined to be a continuous random variable; rather, it may possibly be a discrete one or a mixture of both; see, e.g., Takagi (1991)) Thus, substituting λC = λD / Δ and SC = SD ⋅Δ into E[NC] and E[WC] of Table 2, we have approximations for E[ND] and E[WD] as follows:

    E [ N D ] E [ N C ] = ( λ D / Δ ) 2 E [ ( S D Δ ) 2 ] 2 ( 1 ρ D ) = λ D 2 E [ S D 2 ] 2 ( 1 ρ D ) ,
    (2)

    E [ W D ] E [ W C ] / Δ = ( λ D / Δ ) E [ ( S D Δ ) 2 ] 2 ( 1 ρ D ) / Δ = λ D E [ S D 2 ] 2 ( 1 ρ D ) .
    (3)

    Comparing (2) and (3) with their exact Geo/G/1 counterparts in Table 2, we obtain the absolute and relative errors as given in Table 3 below:

    Note first that since the right-most sides of (2) and (3) and their errors given in Table 3 do not depend on Δ , the accuracies of the approximations do not get better at all, even when the discrete-time system has an extremely tiny Δ . Also, note that these approximations always overestimate the exact calculations and that the absolute errors thus obtained can grow considerably large as the traffic intensity ρD gets close to one. It is remarkable to note further that the relative errors in Table 3 depend not on the traffic intensity (nor on the slot duration), but only on E [ S D R ] = E [ S D 2 ] / 2 E [ S D ] 1 / 2 , the mean residual service time, i.e., the mean number of slots that remain to be completed for the customer in service (Takagi, 1993). That is, for a given E [ S D R ] , the relative errors are constant for all other parameter values! When the service time is a constant d slots, for example, the relative errors specialize to 1 / (d −1) . When the service time is geometrically distributed with parameter μD , they specialize to μD / (2 − 2μD) ; hence, they can grow to infinity as μD gets close to one, resulting in substantially large relative errors for the entire range of the traffic intensity.

    Remark 1. In this remark, we consider a deterministic- service Geo/D/1 queue, in particular, that is approximated with the corresponding M/D/1 counterpart. Let us call a part of the approximation error “distributiondiscrepancy error” that is caused by approximating the distribution of a discrete random variable of either the interarrival time or the service time with the distribution of its continuous counterpart. It is obvious to see in this deterministic-service case that the distribution-discrepancy error arises only from the interarrival-time distribution (under the M/G/1 setting, in general, the distributiondiscrepancy error is not caused by the service-time distribution, as discussed earlier, but only by the interarrivaltime distribution). It can be seen from sample numerical results of Table 4 that the absolute errors increase considerably as the traffic intensity gets close to 1. Furthermore, note from Table 5 that the relative errors stay the same, depending only on E [ S D R ] = ( d 1 ) / 2 ; it does not matter how nicely the Bernoulli arrival process (with tiny λD ) is approximated with its Poisson counterpart. Along these lines, consider a rather extreme Geo/D/1 case, having d =1 , a constant, which is the first case of Table 4. In this case, it is trivial to see that E[WD] = 0 is approximated with E[Wc] ≠ 0 , resulting in an infinite relative error. In such a case, note that the relative error can be significantly large, even if the distribution-discrepancy error (arising from interarrival-time distribution) can be negligible. We further discuss how the absolute and relative errors originate in the following remark.

    Remark 2. In this remark, we discuss how the difference between E[W] of the Geo/G/1 and M/G/1 queues originates (the difference is given by ρD / 2(1−ρD) ; see Table 3). To this end, we let E[SR] represent (for both queues) the mean residual service time of the on-going service, which an arbitrary customer arrives to find. Then, we apply the so-called delay cycle analysis to both queues (The delay cycle is made up of the 0th generation (also called the initial delay) of the delay cycle (SR in this case) and all the subsequent generations of the delay cycle, where the ith generation of the delay cycle is the period for serving all the customers that arrive during the (i −1) th generation; see, e.g., Takagi (1991, 1993)). As a result, E[W] for both the Geo/G/1 and M/G/1 queues is represented as follows:

    E [ W ] = ( 1 ρ ) 0 + ρ { E [ S R ] + E [ S R ] λ E [ S ] + E [ S R ] λ E [ S ] λ E [ S ] + } , = ρ ( 1 ρ ) E [ S R ]
    (4)

    In a discrete-time model, recall that arrivals and departures take place only at slot boundaries, whereas they take place at any point in time in its continuous-time counterpart. As a result, E[SR] for the M/G/1 model is given by E [ S C R ] = E [ S C 2 ] / 2 E [ S C ] , whereas the same for the Geo/G/1 model is given by E [ S D R ] = E [ S D 2 ] / 2 E [ S D ] 1 / 2 . Note that this difference of 1/2 in E[SR] (of the initial delay) generates all the subsequent differences between these two queues. When ρ D = λ D E [ S D ] is large, the initial difference of 1/2 in E[SR] is more likely to reproduce subsequent generations of the delay cycle, so that this slight initial difference multiplies to grow as big as ρ D / 2 ( 1 ρ D ) for E[W] (and λ D ρ D / 2 ( 1 ρ D ) for E[N] ), and it can grow considerably large, particularly as ρD gets close to 1. When ρD is small, on the other hand, the initial difference of 1/2 in E[SR] is less likely to reproduce subsequent generations of the delay cycle, so that the initial difference does not bring about as much effect as in the case of large ρD , resulting in a smaller difference between these two queues. In addition, it is easy to see from (4) how the relative error for E[W] (as well as the same for E[N]) simplifies to ( 1 / 2 ) / E [ S D R ] (as given in Table 3). Thus, when [ ] RD E S is relatively large, compared to the difference of 1/2 in E[SR] , the relative error is small; otherwise, it can be considerably large for the entire range of the traffic intensity.

    Remark 3. In this remark, we discuss when the approximation of the Geo/G/1 queue with its M/G/1 counterpart works well. For the absolute error (e.g.,ρD / 2(1−ρD) ) to be small in this approximation, it is obvious to see that ρD needs to be small. Therefore, a large mean interarrival time (equivalently, a small λD , resulting in a small distribution-discrepancy error) is not good enough; further, it should be extra-large compared to the mean service time, so that ρD is small. Besides, for the relative error ( ( 1 / 2 ) / E [ S D R ] ) to be (constantly) small, E [ S D R ] needs to be large; for example, when the service time is a constant d slots, where E [ S D R ] = ( d 1 ) / 2 , the constant service time d needs to be large; when the service time is geometrically distributed with parameter μD , where E [ S D R ] = ( 1 / μ D ) 1 , the mean service time (1/μD) needs to be large. Hence, in order for the approximation to work well in these two examples, the mean service time needs to be large first of all (so that the relative error is small) and then the mean interarrival time needs to be even larger than the mean service time (so that ρD is small, resulting in a small absolute error).

    4. APPROXIMATING THE GEOX/G/1 QUEUE WITH ITS MX/G/1 COUNTERPART

    In this section, we discuss how the approximation and its error become when the batch-arrival GeoX/G/1 queue is approximated with the MX/G/1 counterpart. In the batch-arrival GeoX/G/1 (MX/G/1) queue, groups of customers arrive according to a Bernoulli (Poisson) process with parameter λ D G   ( λ C G ) . For both the GeoX/G/1 and the MX/G/1 queues, the number of customers in an arriving group is represented by a discrete positive random variable G (for G, we don’t use subscripts C nor D). All of the notations stay the same as in Section 3, except for the traffic intensities ρ D = λ D G E [ G ] E [ S D ] < 1 and ρ C = λ C G E [ G ] E [ S C ] < 1 .

    Now, we consider an arbitrary customer in a group, which we call a tagged customer. Then the number of customers in this group who are served earlier than this tagged customer is represented by GR , whose mean is given by E [ G R ] = E [ G 2 ] / 2 E [ G ] 1 / 2 (Takagi, 1991). Then the performance measures of primary interest, i.e., E[N] and E[W] are given by Table 6 below. For their derivation, see, e.g., Takagi (1991, 1993).

    In Table 6, note that the first terms of E[N] and E[W] represent the additional quantities that are brought in by the batch arrivals. In addition, it can be seen that E[ND] and E[WD] for the discrete-time GeoX/G/1 queue have the terms λ D G E [ G ] ρ D / 2 ( 1 ρ D ) and ρ D / 2 ( 1 ρ D ) , respectively, that do not correspond to E[NC] and E[WC] for the continuous-time MX/G/1 counterpart.

    For an approximation of the GeoX/G/1 queue with the corresponding MX/G/1 queue, we use λ D G / Δ for λ C G , SD ⋅Δ for SC , along the same lines as we have done for the single-arrival case. Substituting λ C G = λ D G / Δ and S C = S D Δ into E[NC] and E[WC] of Table 6, we have approximations for E[ND] and E[WD] as follows:

    E [ N D ] E [ N C ] = ρ D E [ G R ] ( 1 ρ D ) + ( λ D G E [ G ] ) 2 E [ S D 2 ] 2 ( 1 ρ D )
    (5)

    E [ W D ] E [ W C ] / Δ = E [ G R ] E [ S D ] ( 1 ρ D ) + λ D G E [ G ] E [ S D 2 ] 2 ( 1 ρ D )
    (6)

    Comparing (5) and (6) with their exact GeoX/G/1 counterparts in Table 6, we obtain the absolute and relative errors as given in Table 7 below.

    Note that the absolute errors thus obtained in Table 7 are the same as in the case of single arrivals, except that λD of the single-arrival quantity is replaced by λ D G E [ G ] of its batch-arrival counterpart. Their relative errors, on the other hand, are partly different. It is simply because E[ND] and E[WD] (as well as E[NC] and E[WC] ) have the additional (first) terms as noted above that are brought in by the batch arrivals. Along the same lines as in the single-arrival case, note that the absolute errors in Table 7 do not depend on the slot duration and they can grow considerably large as the traffic intensity gets close to one. It is still remarkable that their relative errors depend not on the slot duration nor on the traffic intensity but only on the first two moments of the service time and the group size.

    Remark 4. To better understand the relative errors in Table 7, particularly, the term E [ G R ] / λ D G E [ G ] , we let the number of customers that arrive at a slot be represented by Λ (note that Λ may have a value zero). Then G can also be represented by Λ as a conditional random variable: G = Λ | Λ > 0 . From this, we have E [ G R ] / λ D G E [ G ] = E [ Λ R ] / E [ Λ ] , where E [ Λ R ] = E [ Λ 2 ] / 2 E [ Λ ] 1 / 2 . For better interpretation, we replace E [ G R ] / λ D G E [ G ] with E [ Λ R ] / E [ Λ ] hereafter. Note that E [ Λ R ] / E [ Λ ] can be interpreted as the proportion of customers, among those who arrive at a slot, that are served before a tagged customer. When Λ has a Poisson distribution, for example, E [ Λ R ] / E [ Λ ] specializes to 1/2 (not depending on the parameter of the Poisson distribution). For another example, when Λ has a geometric distribution with support {0,1, 2,⋯} , (i.e., the number of failures of Bernoulli trials until the first success), E [ Λ R ] / E [ Λ ] specializes to 1 (not depending on the parameter of the geometric distribution).

    5. APPROXIMATING A DISCRETE-TIME TANDEM NETWORK WITH ITS CONTINUOUS-TIME COUNTERPART

    In this section, we consider an approximation of a discrete-time queueing network with its continuous-time counterpart. Since a simple product-form solution is not available for a discrete-time queueing network, in general, we confine ourselves here, in particular, to a discrete-time tandem network, in which n nodes of discrete-time singleserver queues with geometric service times are in tandem. We assume that customers arrive at the first node according to a Bernoulli process with parameter λD and they are served for geometric service times with parameter μ D 1 on a FIFO basis. As soon as the service for a customer is over at the first node, she moves on to the second node and is served for a geometric service time with parameter μ D 2 on a FIFO basis, and so on, until she leaves the network for good after getting the last service from the nth node. It is assumed that except for the first node, customers arriving at a node are only those departing from the preceding node; that is, no external customers are admitted to this tandem network but to its first node. It is also assumed that the service time of a customer at a node is independent of everything else.

    Let us imagine a situation, in which one needs to obtain the mean number of customers (E[ND]) waiting in this discrete-time tandem network (excluding those in service) and the mean number of slots (E[WD]) that a customer spends waiting in this network (excluding her service times), and cannot help but approximate this discretetime network with its continuous-time counterpart, presuming that the latter can serve as a good approximation to the former. In order to make use of the simple product-form solution for the celebrated Jackson network, one of the reasonable ways, which we use in this paper, is to approximate the Bernoulli arrival process having parameterλD with the Poisson process having rate λC =λD / Δ , and to approximate the geometric service times with parameter μDi with the corresponding exponential distributions with parameter μCi =μDi / Δ for i =1, 2,⋯, n. As a result, E[ND] and E[WD] are approximated as follows:

    E [ N D ] E [ N C ] = i = 1 n { ρ C i 2 ( 1 ρ C i ) } = i = 1 n { ρ D i 2 ( 1 ρ D i ) }
    (7)

    E [ W D ] E [ W C ] Δ = i = 1 n { ρ C i μ C i ( 1 ρ C i ) } Δ = i = 1 n { ρ D i μ D i ( 1 ρ D i ) }
    (8)

    where the traffic intensities are given by ρ C i = λ C / μ C i = λ D / μ D i = ρ D i < 0 for i =1, 2,⋯, n. Note that (7) and (8) are simply the summations of the mean numbers of customers and the mean queue-waiting times of the individual M/M/1 nodes, respectively.

    Fortunately, this discrete-time tandem network is one of just a few cases, in which a remarkably simple product- form solution is available (Hsu and Burke, 1976). The exact results are given as follows:

    E [ N D ] = i = 1 n { ρ D i 2 ( 1 ρ D i ) λ D ρ D i ( 1 ρ D i ) }
    (9)

    E [ W D ] = i = 1 n { ρ D i μ D i ( 1 ρ D i ) ρ D i ( 1 ρ D i ) }
    (10)

    These are simply the summations of the mean numbers of customers and the mean queue-waiting times of the individual Geo/Geo/1 nodes.

    Comparing (7) and (8) with (9) and (10), it is clear to see that these approximations (7) and (8) always overestimate exact calculations (9) and (10), with the absolute errors, given by i = 1 n λ D ρ D i / ( 1 ρ D i ) and i = 1 n ρ D i / ( 1 ρ D i ) , respectively. Note again that these errors do not depend on the slot duration Δ ; it is just irrelevant. Further, these absolute errors can get considerably large, due to any one of ρi that is close to one. To demonstrate this error, we present Figure 1 that displays the numerical differences between approximate and exact values for the mean queue-waiting time in the first node alone, where we set μ D 1 = 0.5 with various λD ranging from 0 to 0.495 and ρ1, accordingly, ranging from 0 to 0.99. In this demonstration, note also that approximate values are always two times greater than the exact counterparts.

    In fact, note that approximating this discrete-time tandem network with its continuous-time counterpart boils down simply to approximate each Geo/Geo/1 node of this discrete-time network with the corresponding M/M/1 node. Along these lines, see Table 8 for E[N] and E[W] for the M/M/1 and Geo/Geo/1 queues and Table 9 for the absolute and relative errors brought about by approximating the Geo/Geo/1 queue with its M/M/1 counterpart (In this approximation, the distribution-discrepancy error arises from both the interarrival-time and servicetime distributions). Note from Table 9 that the absolute errors can grow huge as ρD gets close to 1. Moreover, note that the relative errors can also grow huge as μD gets close to 1, no matter how nicely the Bernoulli arrival process is approximated with the corresponding Poisson process.

    For this discrete-time tandem network, fortunately, the exact result is available. However, this may not be always the case in general. Suppose a discrete-time version of the Jackson network, in which a customer completing her service at a certain node may join one of any nodes in the network, or external arrivals are admitted not only to the first node but also to other nodes in the network. Since little results are available for such a discretetime network, in general, one may be inclined to resort to an approximation with its continuous-time counterpart. As we have demonstrated above, however, such an approximation can be significantly defective and thus misleading for a considerable range of parameter values.

    6. CONCLUSIONS

    In this paper, we discuss the performances of approximations of discrete-time queues with their continuous-time counterparts. As we demonstrate throughout the paper, such approximations can be easily misleading. Taking the single-arrival Geo/G/1 queue, the batch-arrival GeoX/G/1 queue, and the discrete-time tandem network for examples, we demonstrate that no matter how small the slot duration is, such an approximation always overestimates and brings about a considerable absolute error that tends to grow considerably large as the traffic intensity gets close to one. We show, in addition, that its relative error depends not on the slot duration nor on the traffic intensity, but only on the first two moments of the service time (and on the group size in case of batch arrival). Consequently, this relative error can be substantially large for the entire range of the traffic intensity, even if the Bernoulli arrival process is nicely approximated with the corresponding Poisson arrival counterpart. Furthermore, the probability (λD) that a customer arrives during a slot is not a controllable variable in practice but it is predetermined by the given discrete-time system, such that one may not approximate the arrival process as nicely as he or she desires.

    In conclusion, special attention has to be paid to such approximations, and further sophisticated analysis needs to be carried out for more accurate evaluation of the discrete- time queueing systems, taking their discrete-time characteristics into account. As is mentioned in the Preface of Woodward (1994), “It is better to have an approximate treatment of an accurate model than an accurate treatment of an inaccurate model.”

    ACKNOWLEDGMENTS

    The first author’s work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2019R1F1A1046472). The second author’s work was supported by 2020 Hannam University Research Fund. The third author’s research was supported (in part) by the Department of National Defense CDARP grant GRC0000B1638.

    Figure

    IEMS-19-2-358_F1.gif

    Approximate and exact mean queue-waiting times for the first node.

    Table

    Approximation of the geometric distribution with its exponential counterpart

    Performance measures of M/G/1 and Geo/G/1 queues

    Errors brought about when approximating Geo/G/1 with M/G/1

    Absolute error grows as ρ gets close to 1

    Relative errors stay the same even as λD gets extremely smaller

    Performance measures of MX/G/1 and GeoX/G/1 queues

    Errors brought about when approximating GeoX/G/1 with MX/G/1

    Performance measures of M/M/1 and Geo/Geo/1 queues

    Errors brought about when approximating Geo/Geo/1 with M/M/1

    REFERENCES

    1. Alfa, A. S. (2016), Applied Discrete-Time Queues, Springer.
    2. Bruneel, H. and Kim, B. G. (1993), Discrete-Time Models for Communication Systems Including ATM, Kluwer Academic Publishers.
    3. Chaudhry, M. L. and Goswami, V (2019), The queue Geo/G/1/N+1 Revisited, Methodology and Computing in Applied Probability, 21(1), 155-168.
    4. Daduna, H. (2011), Discrete time networks with product form steady states. In: R. J. Boucherie, N. M. van Dijk (eds.), Queueing Networks: A Fundamental Approach , Springer, 269-312.
    5. Harchol-Balter, M. (2013), Performance Modeling and Design of Computer Systems: Queueing Theory in Action, Cambridge University Press, New York.
    6. Hsu, J. and Burke, P. J. (1976), Behavior of tandem buffers with geometric input and Markovian output, IEEE Transactions on Communications, 24(3), 358-361.
    7. Kim, N. K. , Chae, K. C. , and Chaudhry, M. L. (2004), An invariance relation and a unified method to derive stationary queue-length distributions, Operations Re­search, 52(5), 756-764.
    8. Kleinrock, L. (1976), Queueing Systems, Volume 2: Computer Applications, John Wiley & Sons, New York.
    9. Miyazawa, M. and Takagi, H. (1994), Editorial introduction, Queueing Systems, 18(1-2), 1-3.
    10. Stallings, W. (1998), High-Speed Networks: TCP/IP and ATM Design Principles, Prentice Hall, NJ, USA:.
    11. Takagi, H. (1991), Queueing Analysis: A Foundation of Performance Evaluation, Vol. 1, Vacation and Priority Systems, Part 1, Elsevier Science Publishers.
    12. Takagi, H. (1993), Queueing Analysis, A Foundation of Performance Evaluation, Vol. 3, Discrete-Time Systems, Elsevier Science Publishers.
    13. Walrand, J. (1991), Communication Networks: A First Course, McGraw-Hill
    14. Wolff, R. W. (1989), Stochastic Modeling and the Theory of Queues, Prentice Hall.
    15. Woodward, M. E. (1994), Communication and Computer Networks: Modelling with Discrete-Time Queues, Wiley-IEEE Computer Society Pr.