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.

Comments

Why P2P?

[gazbo]

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...

nay say : rogue ants & prisoner's dilema

[DrSkwid]

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

Not really new.

[rutger21]

I did some little research on this subject about two years ago. The goal of the project was complete autonomous network management. It has been a while ago, but IIRC the automatic routing adjustment worked like this:

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.

Limited practical uses

[mortenf]

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.

Re:Rogue ants

[tolan's my name]

Real ants are genetically programmed with loyalty to their hive

This isnt actually true. Many experiments have been done were both adult ants and larve have been transported between hives, usually there is no difference in behavior to native ants.

There are even a number of ant species that have not worker caste of their own and survive by raiding other ant colonies [of a differing species] and stealing larve. These then hatch and act as workers for the new colony.

If ants are genetically programed to do anything it is to react to certain smells

Emergent behavior

[Nyrath the nearly wi]

I read something similar to this a long time ago, how tiny algorithms in individual simulated birds composing a simulated flock would automagically produce large scale flock behavior (the same behavior observed in real life flocks of birds).

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.

Swarm intelligence has been researched for awhile

[goldenfield]

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...