USS Clueless              Voyages of a restless mind

Main: normal long no graphics Contact Log archives Best log entries Other articles Site Search

Stardate 20010803.1056 (On Screen): About 15 years ago I worked for BBN, in the group which was maintaining the hardware which supported the ARPANet. It was near the end of its technological life and was about to be replaced by more modern networking architectures, but for a long time it was state-of-the-art. ARPA wasn't the only customer which used it; there were other companies which at the time needed their own private networks. Airlines were big users, for instance, to connect travel agents and airports to their central reservation systems. Big hotels used them, too. The basic technology was what was known as a "packet switch node" which was connected to between three and six neighbors using 56 kbit lines, the fastest available at the time for any reasonable amount of money. It didn't use "source routing"; rather, a packet travelling from Seattle to Miami might go through San Francisco, Salt Lake City, Denver, Chicago, Atlanta and then reach Miami. At each step, the node would decide based on current traffic conditions in the network where it ought to go next.

Obviously, a network like this can be designed well or badly, and you could get the same performance out of networks 50% different in expense. Customers wanted optimized network designs, and BBN had a group whose job was to design networks for potential customers in hopes of making the low bid. They used genetic programming, a relatively new technique then. They would sit down and manually design a potential network, and then put it into a special program that ran on a dedicated high speed workstation. What that would do is to successively mutate the network, and then evaluate all the children and only retain the best few, then mutate etc. until someone told it to stop. Usually they'd run it for three days or so (representing thousands of generations). There were two invariant results. First, the winning network bore no resemblance to anything a human would design. Second, the winning network would massively outperform the best human design for less money. If you didn't know the mechanistic source of the design, you might describe some of them as "ingenious".

As a problem in genetic programming, this one was quite circumscribed. The "genome" was relatively small, consisting of the number of nodes, their placements (out of no more than a few hundred potential choices most of which were cities) and the interconnections between them. Part of the model would be a description of the expected traffic and that didn't mutate, but it did feed the evaluation heuristic which attempted to determine how well a candidate design would carry that particular traffic pattern. This was about the limit of what was possible with the compute resources available at the time, since the high speed workstation on which this ran used a 25 MHz 68030.

But as we all know, the cost and power of computing has come a long way since then, and it's interesting to read that the same essential approach is now being used, with thousands of times more compute power, to actually design computer algorithms. This is really exciting, and it's the first practical example I've ever seen of a program which really can solve a problem for us without us having to tell it how to do so. All programming until now has involved humans doing the design. In this case we're actually seeing working code which no human described ahead of time. It will be interesting to see how widespread this becomes as computers continue to get cheaper and faster. (discuss)