Impact of complex network properties on routing in backbone networks

The properties found in complex networks (e.g., small-world, scale-free) have been used to characterize the behaviour of several processes such as epidemics or oscillators. We analyze the impact of such properties on the quality of a routing process. Using a Mixed Integer/Linear Program, the routing minimizes the number of ports installed in the network. Ports are network components which we use as a simplification of the capital cost in communication networks. Using data mining techniques, we are able to predict the minimal number of ports of a network with small error rate given the network's properties and under the assumption of a realistic traffic distribution. We find that the average betweenness and the average path length are good indicators of the number of ports. We then present exploratory work on the dynamic aspects by considering that nodes join the network, which corresponds to the deployment of communication equipment. We consider several approaches to deploy the equipment, and report on the number of ports for each approach. By comparing approaches, having less edges can still yield better performances which motivates investigations on the design. Furthermore, this dynamic case confirms the static one since a tradeoff between the average betweenness and the average path length seems to be a key element in efficient designs