Queuing network of scale free topology: on modelling large scale network

The analytical performance model of networks with scale free structure is studied in this paper. The key issue is the mathematical relation between the performance measure and the network structure. A stochastic model of closed queuing network (SQN) within which customer routing between queues may depend on the local information of complex network is presented. In the model, the complex network is decomposed into sub-networks with scale-free characteristics called SN. Given the rule of preferential attachment, the routing probabilities allowed are formulated by the rational functions of the degrees of various neighbors which reside within SN. It is proved that the introduction of these functions will preserve the product form of the equilibrium state distribution. The product form yields the convolution expression of normalizing constant accordingly. A recursive algorithm is adopted to solve the expression effectively. Therefore, the performance measures are presented based on the exact solution of the normalizing constant. Finally, the model is applied to the design and evaluation of communication infrastructure of real large-scale network deployed on Internet.