By Will Knight
Internet download speeds could be improved dramatically by
mimicking Darwin's evolution to "breed" the best networking strategies, say
computer scientists. Transferring popular data across the internet repeatedly
can be inefficient and costly, so networking companies have developed ways
of temporarily storing, or "caching", data at different locations to reduce
costs and increase download speeds. But figuring out where to store data
and for how long is a complex problem. One solution might be to have caches
"talk" to each other repeatedly, but this is inefficient as it takes up a
lot of bandwidth.
To tackle the challenge, Pablo Funes of US company Icosystem and Jãrgen
Branke and Frederik Theil of the University of Karlsruhe in Germany used
"genetic
algorithms", which mimic Darwinian evolution, to develop strategies
for internet servers to use when caching data. Using a simulation they were
able to improve download speeds over existing caching schemes.
The researchers evolved algorithms for specific types of network, for example
networks with a bottleneck. But they also developed algorithms that worked
well on various types of network.
Major intersection
Funes told New Scientist the scheme could eventually be used to allow caches
to automatically "evolve" their configuration. "Further development could
involve different rules suited to each individual host or subnet involved
in the internet," says Funes. "One can even imagine each host evolving its
own optimal rule." The team used a network simulator to test out different
caching strategies. They created a simulation of a branch of internet network
where data could be copied and stored at every major intersection. They used
this simulation to test algorithms used to configure the caches. The algorithms
take known variables, such as the number of times a piece of data is requested,
the number of points it has to pass through and its overall size, and work
out whether it should be stored and for how long. The key to finding an efficient
algorithm was "evolving" it from a population of randomly generated ones.
The starting population of algorithms was tested on the simulator using randomly
generated requests.
Algorithm breeding
The algorithms that reduced network traffic and improved download speeds
best were then used to "breed" a new population of algorithms. Breeding involves
combining different pieces of an algorithm and introducing some random mutations.
The process can be repeated again and again to improve efficiency. When tested
on a simulated network of 300 intersections, or "nodes", the algorithms they
developed were twice as fast as the best existing strategy. "It is quite
neat," says Jon Crowcroft, at the UK's Cambridge University. "The novelty
lies in the rather 'inelegant' algorithm that they evolve."
But Funes admits there are limitations. An important consideration is what
incentives there are for caching information for other users. He suggests
networks might in the future be designed to work out who deserves the most
help for themselves. "Sophisticated network behaviours might implement rules
for reciprocity and
trust," he says. "And
conversely, for not cooperating with other others who try to abuse our
resources." |