evolutionary algorithms for packet switched networks

Date view Thread view Subject view Author view

From: Eugene Leitl (eugene.leitl@lrz.uni-muenchen.de)
Date: Thu Oct 05 2000 - 01:55:11 PDT


Speedy sex

A bit of evolution will work wonders for the Internet

VIRUSES are common on the Internet, but now it's the turn of bacteria,
says British Telecom. But rather than being a menace, the organisms BT
has in mind have been designed to help make the Net faster. The idea
is to mimic bacterial sex to "evolve" a more efficient network.

Ian Marshall at BT's research centre near Martlesham, Suffolk,
believes that the volume of Internet traffic is growing at an
unsustainable rate. "It's important that the network is able to adapt
continuously," he says. BT's solution is to let it manage itself.

Rather than having software oversee the entire network, Marshall and
his colleague Chris Roadknight designed the junctions of a network so
that each could be run by a piece of autonomous software. Like
bacteria, they had no central knowledge or overall control, yet
Marshall says they were able to run the network very efficiently.

Information sent over the Internet is broken up into discrete packets
which are stored in a "buffer" memory before being forwarded to the
next leg of their journey. Ideally, buffers are long. But the more
information the packets hold, the slower they move. "If a packet
arrives at the buffer and it is full, then it tends to get thrown
away," says Marshall. This means some information will be lost.

What is needed is the ability for buffers to know what kind of
information they are passing and adapt their length according to the
need. To do this using traditional techniques will become impossible
as the Internet grows. So BT turned to nature in the form of "genetic
algorithms". These are biologically inspired programs commonly used to
help design--or evolve--things that people find difficult.

GAs mimic natural selection by treating strings of data like genetic
material. These strings can be combined and mutated to produce
offspring whose fitness is then evaluated. The best are "bred" to
produce more offspring. This is repeated until the best design has
evolved. The problem BT found was that GAs are too slow for real-time
applications, since they require the evaluation to take place over
many generations. So Marshall and his colleagues proposed a different
biologically inspired solution.

Bacteria don't have sex in the traditional sense, they reproduce using
a technique known as plasmid migration. "They wander around and bump
into each other and say 'hi, do you want some of my genetic
material'," explains Inman Harvey, an artificial intelligence
researcher at the University of Sussex. By exchanging plasmids (rings
of genetic information) through their cell membranes with neighbouring
cells, successful genes can pass quickly through a colony and allow it
to adapt rapidly to its environment. Random mutations produce new
genes, with successful genes flourishing and ineffective ones quickly
dying off. In a network these successful genes will enable the buffers
to be optimised to carry packets of information as efficiently as
possible. According to Harvey, the technique could open up many

"With evolution, traditionally you only reap the benefits after many
generations, whereas here you have the three aspects of
evolution--heredity, variety and selection--but without anyone having
to die," he adds.

Duncan Graham-Rowe

   From New Scientist magazine, 07 October 2000.

Date view Thread view Subject view Author view

This archive was generated by hypermail 2b29 : Thu Oct 05 2000 - 03:02:28 PDT