  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.
