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.
The BBC had something on this on Tuesday:
d _1 537000/1537645.stm
/.
http://news.bbc.co.uk/hi/english/sci/tech/newsi
Isn't this the way that HEX in the discworld novels works?
Classic
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...
If packets can communicate with each other to give routing info, they can also communicate with the outside world to do the same. This allows packet tracing under all conditions, rather than just ideal conditions as it is now.
324006
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...
eat shit and die, Bambi!
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.
This sounds like a neat idea, but is it actually more than a nice metaphor? ie, how would this look in practice?
The examples the article gives talk about data packets travelling between two destinations (nest and food source) or one data stream travelling between various locations (travelling salesman). Reality in any current network looks pretty different, however - even in the pretty small company I work for (about 50 employees), there are about 200 machines, each with several client and server tasks running at the same time which makes for a hell of a lot of packets to be routed (pretty easy in this example since they are all routed through the same stack of switches, but you get the idea).
For this approach to work, every connection from machine a to machine b would need some sort of unique identifier and then mark its path with its very own pheromones - quite a bit of overhead if you ask me. Imagine billions of simultaneous connections on the internet each leaving a trail of unique identifiers on their way...
(unless you opt for an "intelligent" solution where, say, my connection attempt to slashdot is broken up into several steps like "find best path to isp", "find path from isp to transatlantic cable", etc., but that would require a general map of the whole network's layout already be present on every router - which kind of defeats the whole purpose of ant-routing).
frotz grue
There is going to be a period of time after the food is exhausted that the trail is relatively strong. Gradually diminishing numbers of ants will follow the trail until it is extinct. One solution might be for ants that find no food at the end of a trail to release another chemical along the trail marking it as exhausted. Since trails can branch, the effect of invalidation scent should be to reduce enthusiasm to follow a trail not switch it off. There are many tuning possibilites based on the follow/don't follow chemical ratios. Ants can also have differing proclivities to respond to the two cues.
There will still be a non reducible time that non productive scent trails exist but it and the number of ants that follow them can be kept to a minimum.
To me, these ant-based algorithms seem very similar to genetic algorithms in used in optimization problems: using some random solutions as a seed, modifying them (via trait swaping or deviations from solution, depending on the algoritm,) and looking at some function defining how good the solution is. I realize it's more complicated than that, but that seems to be the gist of it.
In both cases, (ant based and genetic algotithms) it amazes me how much we can still learn from everyday things that we see in nature. I'd love to see what else may be on the horizon.
Maybe there needs to be two different types of ants. First, there needs to be a scout type that goes out and does scavenging to find routes and ensure solid routes exist. This ant will have no payload capacity. Second, there needs to be a worker ant that carries a payload, and has a lower chance of taking a route not already "marked" as good.
;-).
To retrofit our existing network infrastructure, the "scouts" could be installed as a routing protocol, and the "workers" would be IP packets (with a few more bytes of data?) that follow the trails left by the scouts.
[hope]If a big company such as Cisco would jump on this with an extension to IOS, we may very well see this type of routing scheme become very popular.[/hope] It will take a huge undertaking to get something like this off the ground, so I'd bet that we would see a hybrid-ized solution (such as the one I just stated) before we see a new generation of "ant routers" (they would be very small
It's very promising technology. I can't imagine what the future will hold.
LOAD "SIG",8,1
LOADING...
READY.
RUN
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...
You can see some of his papers at: http://citeseer.nj.nec.com/30955.html That is a cool site for any scientifc article lookups. Form that link you can see a lot more of his papers and related ones. Their is a new book coming out about this. I saw it in the article Emergence : The Connected Lives of Ants and their have been others to: Swarm Intelligence
Douglas Calvert
He was speaking of more general ideas like selection and optimization. These of course apply to the Internet, but they apply to a lot of other things too. Someday you'll reread Ant Fugue and exclaim, "Hey! He's talking about x," where x is just about anything.
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
By studying colonies of ants, Ghandi learned how to destroy Colonialism without violence. The sneakernet, or sandalnet to be precise, that he implemented was successful beyond compare.
I'm glad to see that wisdom being applied to packet delivery. Now we only need some witty catch phrase for the standard. Ideas, anyone?
"What is the sound of one belly slapping?"
You can read the detailed discussion on my message board.
:)
There is another article related to this story on BBC.
Ant(Dude) @ Quality Foraged Links (AQFL.net) & The Ant Farm (antfarm.ma.cx / antfarm.home.dhs.org).
With the ability to rate routes via some software protocol what prevents someone from artificially flooding their network with false routing information?
I'd be abit worried if someone created a gravitational hole near doubleclick.net funneling traffic through it; dispite the possibilities of DoS'ing them it'd also mean letting them sniff out marketable data.
- MbM
Foraging techniques (similar to pheremones) are used to propagate meta-info describing how to contact and find other agents within the mesh and the self-organizing, emergent nature of the filesystem owes a debt to random algorithms and similar techniques from ant colonies. The swarm downloading feature we pioneered is also derived from how an ant colony gets food back to the colony, with lots of expendable agents taking individual paths during the delivery task.
While it is sometimes not obvious to casual observers, I think you will find many distributed systems which take their cues from the natural world if you peek under the hood.