Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
The Internet

Better Networking Through Nature 84

Posted by michael from the we-call-this-router-the-Aardvark dept.
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.
This discussion has been archived. No new comments can be posted.

Better Networking Through Nature More

Better Networking Through Nature

Comments Filter:

  • Pratchett right all along (Score:2, Informative)

    by Anonymous Coward
    The BBC had something on this on Tuesday:

    http://news.bbc.co.uk/hi/english/sci/tech/newsid _1 537000/1537645.stm

    Isn't this the way that HEX in the discworld novels works?

    Classic /.

  • we-call-this-router-the-Aardvark dept. (Score:3, Funny)

    by Anonymous Coward on Friday September 14, 2001 @07:52AM (#2297894)
    Wouldn't that be a packet sniffer?

  • Why P2P? (Score:4, Interesting)

    by gazbo ( 517111 ) on Friday September 14, 2001 @07:59AM (#2297917)
    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...
    • A similarity could be found by using the anology of the Napster index to be the "queen ant", since it is the index that provides the directions for the ants to go.

      With out the index, or "queen ant", the Napster network dissipated rather quickly, is shown by the fitering of files on the network. Ant colonies dissipate as well when their queen dies.
    • 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.
    • "The question is, do networks as they exist today really support what people want to do with them? The answer is clearly no."

      I think the last statement is there to help point out where p2p could go. any developments using ants would require changes to current software and/or hardware.

      ants make sense if you consider the file you are searching for to be the food. the food can be in many different places with many paths to each one. in a large file (think feature-length movie), packets would be sent all sorts of different directions over a period of time. ants could concievably be used to make the transfer more efficient the longer it is. for instant messaging, paths are found between the same 2 points for the duration of the conversation. if you have a 'buddy list' those buddies usually exist at the same ip address. more efficient routes could be found even after the conversation ended.
    • Peer to Peer or Client/Server is irrelivent. Packets still need to get from one device to another. TCP/IP packets don't care if it is P2P or Client/Server, either. The ant theory is just a way to develope the most efficient routes between 2 hosts.
    • Some P2P systems actually steal several good ideas from nature, with ant/swarm optimizations being one of the most common ideas used. When designing Mojo Nation [mojonation.net] I stole liberally from swarm intelligence techniques and other evolutionary computing techniques I learned while doing AI research.


      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.

  • Rogue ants (Score:3, Insightful)

    by vandemar ( 82106 ) on Friday September 14, 2001 @08:02AM (#2297930)
    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.

    • Re:Rogue ants (Score:5, Informative)

      by tolan's my name ( 234431 ) on Friday September 14, 2001 @08:11AM (#2297963) Journal
      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
      • 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!
        • No 'The Insect Societies' by E.O.Wilson was my source on this.
          Its an amazing book if you can plow through the zooilogical detail.

          Godel, Escher, Bach by Douglas Hofstater is a great source for Ants and Intelligence. Its a little naive in ways, but its basically the most convincing [and entertaining] book on AI i've come across.
      • I believe it! Microsoft is known for stealing (ahem, buying away) programmers from other colonies. And they've been pretty successful.

  • nay say : rogue ants & prisoner's dilema (Score:4, Interesting)

    by DrSkwid ( 118965 ) on Friday September 14, 2001 @08:04AM (#2297938) Journal
    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. (Score:5, Informative)

    by rutger21 ( 132630 ) on Friday September 14, 2001 @08:07AM (#2297950)
    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.

    • Cool technology!

      Did you do any research on security?
      • Do you require a certain number of ants to show up with successful claims before the chance tables are updated?
      • What happens if many ants are killed along the way (broken cable)?
      • What if someone were to modify the ant's success rate (man-in-the-middle attack)?
      • What if some script kiddie gets a really big magnifying glass?
      • Security wasn't really considered yet - the most important goal was to get the network in a stable state.

        Chance table adjustment was done using the outcome of a formula with travel time as a parameter. Naturally the shorter the travel time, the more "chance" this route gets added

        I'm not quite sure how broken cables were handled exactly. I think it was supposed to be managed by the routers itself.

        success rate depends on travel time (or arrivel times at routers). I suppose a router could digitally sign a timestamp or something.

        most script kiddies have two of those things sitting right on their nose!

  • ant colony optimization (Score:3, Interesting)

    by t0mmyb ( 443620 ) on Friday September 14, 2001 @08:10AM (#2297959)


    This idea has also been applied to areas other than network routing. Do a search on 'ant colony optimization' to learn more... [yahoo.com]
  • 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.

  • Limited practical uses (Score:4, Informative)

    by mortenf ( 191503 ) on Friday September 14, 2001 @08:10AM (#2297962) Homepage
    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 [wasab.dk]).

    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.

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


      Every file is a node. Every P2P app instance is a router. File searches become route lookups.

    • I was under the impression, from my computer science classes, that bin packing was polynomial-time reducable to shortest path. In fact, I probably had to prove that at one point. So ants should be equally good ("good" in a CS sense) at solving all NP-complete problems (such as traveling salesman), no? Is it just not "practical"?
  • that I'd find my router under the kitched table, eating crumbs.

  • Spidergoats? (Score:3, Funny)

    by imadork ( 226897 ) on Friday September 14, 2001 @08:15AM (#2297974) Homepage
    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)

  • Emergent behavior (Score:4, Informative)

    by Nyrath the nearly wi ( 517243 ) on Friday September 14, 2001 @08:18AM (#2297993) Homepage
    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.

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

    • Re:Emergent behavior (Score:3, Informative)

      by DrSkwid ( 118965 )
      as far as i understand it (it was in the execllent "Predators" series on the bbc a couple of weeks ago) the ants are not as auto as that.

      This was for Army Ants :

      They lay a trail on the outgoing journey.

      Each day the ants leave in a different direction to yesterday, covering about a 45 degree arc. and differing in direction about 135 degrees every day so they don't go near yesterdays trails but eventually cover the whole 360 degrees.

      Once complete they move on and choose a different starting location.

      The tv show did en excellent graphic of what was happening.

      They do indeed lay a different trail when returning with food.

      The behaviour is more complex than just rules #1 & #2
    • This is pretty much what my Ant simulation program does [yi.org]. Check it out, it makes interesting pictures!!

      There are some problems when the food runs out, because the ants continue to follow the scents until they run out.

      There's a windows executable version and GPL source code for linux.

      Cheers,
      ben
  • Anthill inside (c)
  • Anybody else remember Aunt Hillary from Douglas Hofstadter's 1979 book [fatbrain.com]? 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.

    • Hofstadter wasn't speaking of the internet in his books, but often he might just as well have been.

      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.

    • Thank you!!! I was trying to remember where I read that. The book was "The Mind's I". The ant colony metaphor was, in my opinion, his strongest of the book.

      ... but I read it a very long time ago.

  • hmmm (Score:2, Insightful)

    by ferkelparade ( 415620 )
    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).

  • ant networking (Score:2, Interesting)

    by mks180 ( 442267 )
    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.
  • It seems to me this is, at a meta level, very similar to genetic algorithm [everything2.com] development.

    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.

  • Retrofit (Score:2, Interesting)

    by eric2hill ( 33085 )
    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.
  • 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

    Some links are
    The 24 January 1998 issue
    http://www.newscientist.com/hottopics/ai/antinmy ph one.jsp

    The 16 November 1996 issue
    http://www.newscientist.com/hottopics/ai/rampant se x.jsp
    (for those scared of goat.cx, rampantsex.jsp is a pheromone thing :-) )
  • 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_1 542000/1542539.stm [bbc.co.uk]

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

  • Swarm intelligence has been researched for awhile (Score:5, Informative)

    by goldenfield ( 64924 ) on Friday September 14, 2001 @09:36AM (#2298319) Journal
    There are actually quite a few uses for this type of technology (see my Master's thesis for references [uiowa.edu]). 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 [swarm.org] - 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...

  • Further Reading... (Score:2, Informative)

    by dfelznic ( 8812 )
    You can see some of his papers at: http://citeseer.nj.nec.com/30955.html [nec.com] 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 [amazon.com] and their have been others to: Swarm Intelligence [amazon.com]
  • Check out My home page [yi.org] 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.

  • 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?

  • You can read the detailed discussion [ezboard.com] on my message board.

    There is another article related to this story on BBC [bbc.co.uk]. :)

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

Slashdot Top Deals

"You'll pay to know what you really think." -- J.R. "Bob" Dobbs

Close