Waiting Time Sensitivities of Social and Random Graph Models

Large scale simulation studies, such as routing in communication systems, rely on complex networks. However, the specific network structure of the application domain is often neglected in analysing network behaviour with the consequence of limited ability to conduct a sensitivity analyses. Network evolution models have been developed to account for structural properties of social graphs, such as the Internet, and enable a model-based analysis on different scales. Despite some analytical results with respect to queueing metrics, little work has been done to frame network evolution models in the context of queuing systems. This paper addresses this issue discussing social and random network evolution models and their application to queueing systems. When the stability criterion holds, analytical solutions using Jackson´s Theorem and Little´s Law exist and provide valuable insights into a number of queueing performance metrics. Specifically, a sensitivity analysis of the mean total waiting time versus the utilisation is carried out which shows a significant difference between the social and random network models. Understanding the impact of the structural features of complex networks is important in the design of simulation studies and operating real world systems. This is especially true when adaptive algorithms are employed and insights of their performance compared to analytical scenarios are required.