Delay Analysis Of Infinite-state Varying Rate Service Process

With the rapid development of modern computer systems,some sophisticated system cannot be analyzed by traditional queueing network theory,such as multi-state varying rate wireless channels,volunteer computing systems and P2P file sharing systems.These systems share a common character:varying rate service,and the number of states is large and even infinite sometimes.For example,in P2P file sharing systems,users downloads files from several other users simultaneously.Suppose all the users have the same uploading rate,the downloading rate of a specific user is proportional to the number of other users that he can connect to.Thus,the downloading rate increases with the number of users in the system.The number of service state is the same as the possible number of users in the system,which is a quite large number.During the service of a downloading task,the downloading rate varies with the user arrivals and departures.These kinds of systems are difficult to analyze and even unsolvable when the number of states is large.In this paper,we analyze one kind of infinite-state varying rate service process.The main contribution of this paper is the two delay bounds and an approximate mean queue formula for this system.In this paper,we model the infinite-state varying rate service process as a M/MMSP/1 queue.The system possess a single server queue with first-come-first-service(FCFS)policy.The server has infinite number of service states each with different service rate,and the state transition between service states is controlled by a continuous time Markov chain.In our model,the continuous time Markov chain of the server state transition is the same as M/M/? queueing model.The service rate at the ith state is i?c where ?c is a constant that represents service rate of a single server.Therefore,taking the job arrival and departure into consideration,the overall system can be described using a two-dimension continuous time Markov chain.However,the Markov chain is irreversible and there is no systematic way to solve the steady state probability of this Markov chain.Therefore,in this paper,we analyze the physical character of the system.At first,we analyze how service rate fluctuation influence the delay performance.Then we obtain the upper bound and lower bound of mean delay and finally provide an approximate mean queue length formula using convex combination of the two bounds.From simulation,we observe that both mean and the second moment of the service time increase with service rate fluctuation when keeping service capacity ? constant.From P-K formula for M/G/1 queue,we know that mean queue length increases with both mean and the second moment of the service time.Therefore,if we keep service capacity constant,system mean queue length will increase monotonically with service rate fluctuation.And the system mean queue length will reach upper bound when the variance of service rate approaches to infinity and reach lower bound when the variance of service rate approaches to 0.In traditional queueing theory,when service rate is larger than job arrival rate,the mean queue length is always finite.On the other hand,when service rate is smaller than job arrival rate,the mean queue length will approach to infinite.Therefore,the percentage of time when service rate is smaller than job arrival rate will influence the mean queue length.From this point of view,we obtain an approximate mean queue length formula using convex combination of the two bounds.At last,we verify the accuracy of our approximation in different ways.Simulation result shows that our approximation is consistent with the actual behavior of the system.Limiting case analysis shows that our approximation can degenerate to lower bound or upper bound in all limiting cases.We also provide a comparison between our approximation and P-K formula and find they have the same structure.From these clues,we believe that the approximation have a quite high accuracy.However,up to now,we know that there is no systematic way to solve this kind of irreversible Markov chain.And this paper could be the spur for many researchers to embark on rigorous proofs of this formula in the future.