Slashdot Mirror
Better Networking Through Nature
The New York Times has an interesting piece about applying lessons from nature - specifically ant colonies - to solving networking and other problems. Not quite on the same level as Spidergoats, but intriguing nonetheless.
Wouldn't that be a packet sniffer?
I remember thinking this was a neat idea a year or so back, when there was a paper about 'ant technology' being used as an efficient algorithm for the travelling salesman problem (mentioned in article).
Applying this to packet routing seems a really elegant idea, there are obvious similarities between optimising packet transport between sites and ant trails to food sources. What confuses me is the talk about P2P networks at the end of the article. It seems to be thrown in to jump on the P2P bandwagon: I mean, where's the similarity between Napster (mentioned by name in the article) and an ant colony? Well, there's no central intelligence (server) and...err..thats it?
Applying ant technology to solve a related problem is a potential solution to that problem. Spotting a vague similarity between two fashionable technologies does not automatically mean that that they are actually relevant to each other. Unless of course he's thought of something and not put it in the article...
Those of us who have played Sim Ant before would probably see some advantages to using "pheremone" based routing on the internet. There is a fundamental difference, however, between real ants, and computers on the internet. Real ants are genetically programmed with loyalty to their hive. Computers, on the other hand, are plagued with script kiddies, worms and greedy lawyers.
The potential for havoc is high if this scheme is ever implemented and script kiddies all over start leaving fake "pheremone" trails around the internet.
All very well but I would suspect that for this to become effectove the packets execute code along their path.
The 'intelligent agent' was supposed to do this too (searching for you while you're not online).
There will be a flip side to it (there always is).
my wild speculation suggests rogue ants laying false trails, viruses tricking the packets into laying false trails, etc. etc.
Also for the internet the bandwidth isn't common property. Peering partners would end up playing prisoner's dilema with "should I make their packets take worse routes from our packets".
that's my criticism ne way
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
a whole bunch of ants are randomly created at all routers in the network, with a mission to get to a random desitination
each router keeps a chance-table for each outgoing port for each destination (in the network), initially all outgoing ports have the same chance
ants start moving, pick an outgoing port randomly according to the chance table
ants remember their path and travelling time
if an ant reaches its destination, the trial it put down on its way over there affects the chance table in a positive way using the memory of the ant
It was rather fun, if I "removed" a router, ants really got adopted fast and found alternative routes. With redundant networks, routers started sending 50/50 to outgoing ports reaching the same destination. An{t,d} of course, as usual, many parts of this algorithms can be improved.
This idea has also been applied to areas other than network routing. Do a search on 'ant colony optimization' to learn more...
While the principle of using ants is hardly news - Dorigo started his more than a decade ago - the use of ant colonies is not suitable for all problems of distributed nature.
I have worked on using ant colonies, basically a variation on Dorigos work, on problems related to floor planning and bin packing (those with danish capabilities could have a look here).
It seems as though the ants are very good at solving the "basic" problems of finding a shortest path, but that the method does not lend well to other optimization problems, even though it may seem that they over time should be able to figure out the best solution.
Routing on the Internet might be a problem that's worth attacking with this method, but aside from the similar issues, I can't see how this would benefit P2P networks.
Don't make fun of my speling, english is my 2nd language...
My policy is to not click on any link at Slashdot that mentions Goats. Peiod.
Naturally the facination is with the big dividends paid to a tiny initial investment in algorithm.
Basic ant food gathering behavior exibits finely tuned feedback and efficency with similar tiny algorithms.
A scout ant searches for food. When it finds it, algorithm #1 kicks in:
- Grab as much food as you can carry.
- Run to the nest.
- If and only if there is food left at the site, leave a scent trail as you go to the nest.
Ants at the nest who are unassigned to task, upon smelling the scent execute algorithm #2, which is basically "follow the scent trail".As more ants grab food and leave scent trails to the nest, the intensity of the scent induces more and more ants to execute algorithm #2.
When the food source is exhausted, no more scent is deposited on the trail, and the scent trail dissapates.
There are actually quite a few uses for this type of technology (see my Master's thesis for references ). The AI community has been looking at swarm intelligence and multi-agent systems for years. NASA has sponsored research on using ant-like behavior in multiple robots to explore Mars (advantages in redundancy, system memory, command and control, etc...).
Also, check out The Swarm Development Group - you can download some software to play with alife sims, visualize really efficient search patterns, etc...