مدل های صف بندی برای ارزیابی عملکرد شبکه کامپیوتری: تحلیل حالت گذرا Queueing Models for Performance Evaluation of Computer Networks—Transient State Analysis

1 Introduction Queueing theory has many applications but performance evaluation of computer networks and computer systems seems to be the most important one. The origins of queueing theory were also related to the transmission of information: first queueing models were proposed a hundred years ago by Agner Krarup Erlang to evaluate the performance of Copenhagen telephone exchange [1, 2] and by Tore Olaus Engset, traffic analyst and then director of Norvegian Televerket (now Telenor Group) [3]. Both of them were studying—already in these days of human operators and cord boards used to switch telephone calls by means of jack plugs—how many circuits were needed to provide an acceptable telephone service or how many telephone operators were needed to handle a given volume of calls. Their analysis was based on Markov models, they assumed that the new connection demands made Poisson process and the duration of connections was given by a negative exponential distribution. In a generic queueing model customers arrive to a service system at random intervals and are served during a random time: if the server is busy serving other customers, the arriving ones are queued. The model is expected to determine the distribution—or at least the mean value—of the number of customers in the system and their waiting time. If the number of customers that may be present in the system is limited, we are also interested in probability of rejection of an arriving customer. Kendall’s notation [4] is used to classify standard queueing nodes: in “A/B/c” A denotes the type of distribution of interarrival times, B—the type of service time distribution, and c the number of parallel servers. The symbol M (memoryless) on the place of A or B means that the corresponding distribution is exponential, Er, Hr Cr denote Erlang, hyperexponential, and Cox distributions of order r, D means deterministic, G is for general distribution, etc. The notation has since been extended to A/S/c/N/H/R where N is the capacity of the queue, H is the size of the customer source (if there are n customers present in a queueing system, it means that H −n may still arrive), and R is the queueing discipline, e.g. FIFO (First-in-First-out) means that the customers are served following the order of their arrival; when the final three parameters are not specified, it is assumed that N = ∞, H = ∞ and R = FIFO, see e.g. [5].