Optimization of transport protocols with path-length constraints in complex networks

José J. Ramasco1, Marta S. de la Lama2,3,4, Eduardo López5,6 and Stefan Boettcher7
1Complex Networks Lagrange Laboratory (CNLL), ISI Foundation, Turin I-10133, Italy.
2Max-Planck Institute for Dynamics and Self-Organization. Bunsenstr. 10, 37073 Gottingen, Germany.
3Instituto de Fisica de Cantabria (CSIC-UC), 39005 Santander, Spain.
4Departamento de Fisica Moderna, Universidad de Cantabria, Santander, Spain.
5CABDyN Complexity Centre, Said Business School, University of Oxford, Park End, Oxford OX1 1HP, UK.
6Department of Physics, University of Oxford, Parks Road, Oxford OX1 3PU, UK.
7Physics Department, Emory University, Atlanta Georgia 30322, USA.

(June 2010)

We propose a protocol optimization technique that is applicable to both weighted or unweighted graphs. Our aim is to explore by how much a small variation around the Shortest Path or Optimal Path protocols can enhance protocol performance. Such an optimization strategy can be necessary because even though some protocols can achieve very high traffic tolerance levels, this is commonly done by enlarging the path-lengths, which may jeopardize scalability. We use ideas borrowed from Extremal Optimization to guide our algorithm, which proves to be an effective technique. Our method exploits the degeneracy of the paths or their close-weight alternatives, which significantly improves the scalability of the protocols in comparison to Shortest Paths or Optimal Paths protocols, keeping at the same time almost intact the length or weight of the paths. This characteristic ensures that the optimized routing protocols are composed of paths that are quick to traverse, avoiding negative effects in data communication due to path-length increases that can become specially relevant when information losses are present.