[unrev-II] Fwd: Better Networks: Look to Nature

From: Jack Park (jackpark@thinkalong.com)
Date: Fri Sep 14 2001 - 07:39:20 PDT

  • Next message: Alex Shapiro: "[unrev-II] Re: Graphs in Web Community Tools - forum?"


    >From: Francis Heylighen <fheyligh@vub.ac.be>
    >>September 13, 2001
    >>Better Networks: Look to Nature
    >>Benoît Doppagne for The New York Times
    >>Marco Dorigo, a computer scientist at the Free University of Brussels, in
    >>his office. Guided by ant behavior, he is studying ways to improve
    >>Internet routing.
    >>HE Internet is an engineering feat of no small magnitude. It operates
    >>using a method of data transmission invented in the 1960's called packet
    >>switching. Send e-mail, for instance, and your message is broken into any
    >>number of little bundles; each takes a separate route and reunites with
    >>the others at the destination.
    >>Over the ensuing decades, as the Internet turned from an academic and
    >>military tool into a mass medium, only the efficiencies of packet
    >>switching have enabled it to meet demand. Even so, as any Web user or
    >>e-mail correspondent can attest, traffic can still be congested and
    >>Now ideas for advances in data routing are beginning to emerge from a
    >>surprisingly simple model: the ant.
    >>Indeed, applying the study of ants to complex engineering problems is
    >>something of an intellectual trend. The topic drew attention at a recent
    >>international conference on artificial intelligence in Seattle. It has
    >>been discussed in a variety of scientific journals. And a new book by
    >>Steven Johnson, "Emergence: The Connected Lives of Ants, Brains, Cities
    >>and Software" (Scribner), points to ant behavior as a way to further,
    >>among other things, understanding of the World Wide Web.
    >>What makes ants worth studying, if not emulating? For one thing, they
    >>exhibit something called swarm intelligence. That is, the teamwork of
    >>social insects is decentralized. Individually, an ant's actions are
    >>primitive, but collectively, they result in efficient solutions to
    >>complex problems like finding the shortest route between the nest and a
    >>food source.
    >>The key to ants' efficiency is their ability to lay down trails in their
    >>communal travels with a chemical called pheromone. Over time, those
    >>trails result in a system of routing. The lesson, in short, is follow the
    >>So to build better data networks, researchers are creating what might be
    >>viewed as artificial ants: small pieces of software that travel through a
    >>network depositing artificial pheromone (pronounced FARE-uh-moan) as they
    >>seek optimal routes.
    >>"By bending the rules of behavior, you can increase the performance of
    >>the system while keeping the spirit of what the ants do," said Vincent
    >>Darley, an ant-behavior specialist and research scientist in the London
    >>office of BiosGroup, a company based in Santa Fe, N.M., that develops
    >>science-based software, routing and marketing strategies for corporations.
    >>Bending the rules can involve giving the ants a memory and enabling them
    >>to retrace a particularly good route so that they can mark it with extra
    >>pheromone — something that real ants do not do.
    >>"Throw a bunch of virtual ants into the cities and each tries to build a
    >>route," said Éric Bonabeau, a physicist and network engineer who has
    >>studied ants and data networks and is the chairman and chief scientist of
    >>Icosystem, a consulting company in Cambridge, Mass.
    >>Marco Dorigo, a professor of computer science at the Free University of
    >>Brussels, has borrowed the ant approach to solve a classic puzzle in
    >>mathematics called the traveling salesman problem. The challenge is to
    >>find the shortest route connecting many different cities — a priority not
    >>only for sales forces but also for systems delivering people, parcels or
    >>packets of Internet data.
    >>As the number of cities involved increases, the difficulty of the problem
    >>can increase exponentially. Just a dozen cities present billions of
    >>possibilities. Apply ant behavior to the traveling salesman problem,
    >>however, and solutions start to present themselves.
    >>In Dr. Dorigo's model, the pheromone deposited along the longer routes
    >>evaporates, leaving the links to the greatest number of short routes most
    >>densely covered with the chemical. When the artificial ants go out again,
    >>they rely on tables storing information about the amount of pheromone on
    >>each link.
    >>Dr. Dorigo has found that repeated trips result in progressively shorter
    >>overall trips. Such work is directly applicable to data networks,
    >>especially the Internet, where traffic is highly unpredictable. Because
    >>the artificial ants in such a model are constantly exploring different
    >>routes, a host of alternatives surface whenever a particular route goes
    >>out of commission.
    >>Dr. Dorigo, who has tested the formulas that he has developed on a
    >>simplified simulator of a packet-switched network that he calls AntNet,
    >>said his aim was to address the shortcomings of routing mechanisms in
    >>systems like the Internet.
    >>The experimental models "are a method for finding very good solutions in
    >>a reasonably short time," he said. "They may not be provably optimal, but
    >>they're very good, which is often what is required in real-world applications."
    >>Dr. Bonabeau said that such models would lead to more efficient, reliable
    >>and robust networks. "But I think the revolution is in the way people
    >>think about networks," he added.
    >>"The Internet is a deeply distributed system, yet people think about how
    >>to regulate its traffic with a centralized mind-set. Swarm-base
    >>decentralized control will lead to entirely new ways of designing networks."
    >>Still, the advances in ant-based networking research have yet to be put
    >>into practice on an actual commercial network, Dr. Bonabeau said. To do
    >>so would require expensive and cumbersome modifications to routing equipment.
    >>Decision makers at communications companies have generally been slow to
    >>embrace the concept, he said. "Especially at France Télécom," where he
    >>was a network engineer, "it's very hard to convince them to let go and
    >>leave the network to ants," he said.
    >>Southwest Airlines (news/quote) has applied some of the lessons of the
    >>ant model to its cargo shipping with aid from BiosGroup. The cargo
    >>solution, said Ruud Schoonderwoerd, a consultant at Pricewaterhouse
    >>Coopers who did some of the early work on ants and routing, illustrated
    >>the importance of balancing network traffic.
    >>"You can optimize something locally but it won't have a global effect,"
    >>he said. "Sometimes it's better to have some routes go a longer distance
    >>so the network as a whole is more balanced." For example, if Southwest
    >>tried to route each package on the first or shortest flight, bottlenecks
    >>could develop that would hamper its routing over all.
    >>Dr. Darley of BiosGroup has applied ant behavior to solving scheduling
    >>problems in complex manufacturing settings and to routing and production
    >>decisions at a natural gas company in Texas.
    >>"In any of these problems, we take the abstract idea of ants' depositing
    >>pheromone and we try to form the right analogy so we can apply the right
    >>technique," Dr. Darley said. "By attaching artificial pheromones to these
    >>various possible decisions, a colony of ants can learn over time what the
    >>best things to do are. So the idea is when this factory breaks down, they
    >>learn they have to start buying gas from a different factory."
    >>Or consider the exploration of a big database of clients, like that
    >>maintained by a bank. Virtual ants can be set loose to wander the
    >>database, picking up pieces of information and depositing them according
    >>to various criteria, resulting in clusters of clients with common
    >>attributes — much the way ants amass clusters of seeds for their
    >>pantries, for example.
    >>"Ant-based algorithms have the potential to improve the efficiency and
    >>reliability of many kinds of complex, dynamically changing systems which
    >>involve routing," Mr. Schoonderwoerd said. "This could be a
    >>telecommunications network such as the Internet, logistic systems such as
    >>factory lines or public transport systems, or perhaps even the design of
    >>integrated circuits."
    >>Understanding ant behavior could also lead to more effective use of the Web.
    >>Mr. Johnson, the author of "Emergence," said that there are distinct
    >>parallels between ant colonies and cities — and by extension, the Web —
    >>in the ways communities are formed.
    >>"If you have an ant colony that only has five ants in it, you can't do
    >>the kind of complex processing that an ant colony does so well," he said.
    >>"You need 10,000 ants for it to do its magic. And for a city neighborhood
    >>to form, you need a big population to see these self-organizing clusters
    >>of like-minded people forming."
    >>Similarly, he said, the seeming chaos of the Web's unfettered expansion
    >>could in fact make it more efficient. "We're now building structures on
    >>the Web that get more useful and more organized as they get bigger, and
    >>in some ways that's what ant colonies and cities do," he said.
    >>The Google search engine, for example, "tracks local decisions made by
    >>individuals to surf from one site to another or add a link from one page
    >>to another, and looks for larger patterns in those decisions," he said.
    >>Thus it ranks results based on the "shared sensibility" of a community.
    >>Likewise, he cited the software program Alexa, a type of Web directory
    >>that can show sites related to the one the user is visiting. Like Google,
    >>Alexa inspects patterns of Web traffic and links sites in a way that
    >>might not otherwise seem obvious.
    >>"Alexa is a way of solving the problem of organizing the Web from the
    >>bottom up instead of the top down," he said. "Alexa says, `O.K., these
    >>sites are related because of the patterns of usage,' so out of that a
    >>higher-level intelligence emerges."
    >>Dr. Bonabeau said he saw a strong similarity between an ant colony and a
    >>so-called peer-to-peer community, a network in which individual computers
    >>are directly connected without the need for a central intermediary.
    >>Napster and other music-sharing services have been prominent if not
    >>notorious examples of such networks; others have been set up to evade
    >>government censorship of the Web in some countries.
    >>Dr. Bonabeau is working to develop ant- based technology that would make
    >>peer-to- peer communities more efficient and foster more synergy within them.
    >>"Peer-to-peer computing, be it peer-to- peer communities, instant
    >>messaging or distributed computing, is a terrific example of where
    >>networks might go," Dr. Bonabeau said. "The question is, do networks as
    >>they exist today really support what people want to do with them? The
    >>answer is clearly no."
    >Dr. Francis Heylighen <fheyligh@vub.ac.be> -- Center "Leo Apostel"
    >Free University of Brussels, Krijgskundestr. 33, 1160 Brussels, Belgium
    >tel +32-2-6442677; fax +32-2-6440744; http://pespmc1.vub.ac.be/HEYL.html

    ------------------------ Yahoo! Groups Sponsor ---------------------~-->
    Get VeriSign's FREE GUIDE: "Securing Your Web Site for Business." Learn about using SSL for serious online security. Click Here!

    Community email addresses:
      Post message: unrev-II@onelist.com
      Subscribe: unrev-II-subscribe@onelist.com
      Unsubscribe: unrev-II-unsubscribe@onelist.com
      List owner: unrev-II-owner@onelist.com

    Shortcut URL to this page:

    Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    This archive was generated by hypermail 2.0.0 : Fri Sep 14 2001 - 08:50:03 PDT