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.
Is it just me, or do pheromones sound like poop?
-- www.globaltics.net
Political discussion for a new world
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?
no, they just kill everything in their path that they can, chop it up and eat it.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
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.
If trying to use DFS to solve the travelling salesman problem doesn't work, how would using this Ants system work?
Running an ant through the map could be equivilant to one DFS search, so how many ants are needed to run through the maze before you find an answer? (and that answer might not be the optimum one either)
Don't quote me on this.
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.
Anthill inside (c)
Anybody else remember Aunt Hillary from Douglas Hofstadter's 1979 book? He uses an ant colony to demonstrate how collective intelligence arises from the interraction of lesser parts, which have no concept of the whole. Here's a passage I like:
Ant colonies have been subjected to the rigors of evolution for billions of years. A few mechanisms were selected for, and most were selected against. The end result was a set of mechanisms which make ant colonies work as we have been describing. If you could watch the whole process as a movie - running billions or so times faster than life, of course - the emergence of various mechanism would be seen as natural responses to external pressures, just as bubbles in boiling water are natural responses to an external heat source. I don't suppose you see "meaning" and "purpose" in boling water - or do you?
And then he goes on to make an amazing connection between the evolution of an ant colony to music!
Hofstadter wasn't speaking of the internet in his books, but often he might just as well have been.
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.
Try searching on Google.
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.
Both were based on processes found in nature.
Both feature very simplistic mechanisms at their heart which aggregate to exhibit larger behaviors.
Both use random choices at the core to drive it all.
Both feature feedback loops that influence the progress of the evolution.
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
Ok nice article, I'm a student artificial intelligence and we learn a lot from looking at how nature solves certain problems.
But why had the writer have to make such an unintelligent uber-irritating explanation on a not so difficult word in his writing that makes me want to throw up on his face?
It's a trend that came with the abbreviation-era when the commerce came to the internet. You see it a lot when people want to have their new buzzword included in day2day(c)marketing/commerce/blabla talk. I understand that it's difficult for those people to learn new hollow expressions and keep up with their affiliates or whatever.
But it's really disgusting to this trend leaking thru in a fairely normal article..
This was covered in New Scientist years ago
y ph one.jsp
t se x.jsp
:-) )
Some links are
The 24 January 1998 issue
http://www.newscientist.com/hottopics/ai/antinm
The 16 November 1996 issue
http://www.newscientist.com/hottopics/ai/rampan
(for those scared of goat.cx, rampantsex.jsp is a pheromone thing
Anyone quoted by a reporter knows how little they understand
Don't believe what you read is the truth.
While obviously not AI in the sense of robots on a human level, this article does bring up the idea of artifical learning. There was an article a little bit ago-- maybe someone can recall and post a link-- about an Israeli institution creating a machine that passed the Turing Test, albeit it was only perceived to be a 6 year old.
What I see in common, and have often thought about as a progression for AI, is their ability not to be programmed everything we know, but start as a child and have the ability to learn as they "grow"; the similarity is in how these "ants" have the ability to learn what the shortest path to a destination is. They can then give that path the most "pheremones" for easy location and also be able to dynamically change the shortest path based on a change in, as the article suggests, a different starting point or loss of nodes (hopefully).
Brand me offtopic, but I believe that this part of internet study could go hand-in-hand with some developments in AI, and vice versa.
Apparently, British Telecom are looking into using bacteria to let all your portable deviceas communicate with each other and do auto configuration for you.
http://news.bbc.co.uk/hi/english/sci/tech/newsid_These devices could get anywhere...
First of all, I read the description of the algorithm and it is not a "solution" to the traveling salesman problem, that problem is NP-1. If someone were to "solve" it as that term is understood by computer scientists, it would be a major advancement in math and computer science. I doubt the algorithm presented could be reduced to mathematically "prove" it can deterministically find the best solution to the problem, and it certainly can't do that in less than O(X^c) time. This is merely a case of a marginal "researcher" who managed to take a weighted paths scheme, perhaps original and perhaps not, and put it in terms that the average reader could nod his head at and say "yeah, I could've told them that! Dumbass scientists."
personal attacks hurt, especially when deserved
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...
Very intersting atricle, and always nice to see articles coming from your Alma Mater...
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
Your router would have to keep state (pheremones in ant-speak). This could chew up considerable CPU resources and storage. Routers are for the most part stateless - and that is a good thing.
I think the analogy between P2P systems such as Napster stands, as the artcle talks about how ant colonies display intelligence that isn't obvious to the individual, and is only evident at a higher level.
This is certainly true with P2P file sharing systems; here popular files are shared more frequently, automatically building in more redundancy, thus improving performance, and old and less popular files are copied less frequently, or are deletd. These are a 'natural' phenomena of P2P file sharing and not an 'engineered' mechanism.
I'm sure that just like the ants, most P2P users are unaware that they are actually an 'agent' in a sophisticated distributed database.
------------ jay*arr*tee
Does this mean we're gonna soon have a RFC-1149A [linux.com] for "ant networking". The packets would have to be pretty small I guess.
Karma...what's that? I just speak my mind.
Did you read it, too?
_Cyberantics_, by Jerry Prosser (writing as "Stanislaw Mayakovsky") and Rick Geary. Brilliant work of fiction which works on so many levels, and would be a plus 5 informative if it were a slashdot post.
Read it!
Check out My home page for an example of an Ant Simulation Program. The blue dot is the ant hill, the green dots are food, the white dots are ants. Red trails lead back to home, green trails lead to food. Each ant is autonomous and lays down pheromones, as described in the article. Enjoy.
it is probably useless even to try to respond to this.
the title of your post exposes this comment as the thoughtless, bigoted swill that it is. use your mind. group hatred is what caused this tragedy in the first place.
you probably shouldn't have read this.
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?"
What most modern scientists don't fathom is that by their definition of smart, and therefore whom is judged as making valid theories, a computer or a file cabinet is the smartest scientist ever. Try using logic and reason, those are things that enjoy facts, and don't let emotional bias make decisions.
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).
The study of ant behavior to design better systems is fascinating, but ants can also be used directly as tools. When I was in graduate school in the 1970s one other graduate student spent his time checking out every ant mound in the Southwestern US. He was looking at what minerals they brought to the surface in their excavation. It became a way to employ lots of cheap field assistants to map geology beneath the alluvium and search for particular minerals.
Yeah, those americans should have stayed out of the middle east.
Angry White Guy
You think that I'm crazy, you should see this guy!
Some years back, a Dilbert strip ran where the PHB forces Dilbert to become an "Ant Farm Engineer". Perhaps now this will be a real job... ;)
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.