Wednesday, August 29, 2012

[tt] the Anternet

Stanford biologist and computer scientist discover the 'anternet'

A collaboration between a Stanford ant biologist and a computer scientist has
revealed that the behavior of harvester ants as they forage for food mirrors
the protocols that control traffic on the Internet.

By Bjorn Carey

On the surface, ants and the Internet don't seem to have much in common. But
two Stanford researchers have discovered that a species of harvester ants
determine how many foragers to send out of the nest in much the same way that
Internet protocols discover how much bandwidth is available for the transfer
of data. The researchers are calling it the "anternet."

Deborah Gordon, a biology professor at Stanford, has been studying ants for
more than 20 years. When she figured out how the harvester ant colonies she
had been observing in Arizona decided when to send out more ants to get food,
she called across campus to Balaji Prabhakar, a professor of computer science
at Stanford and an expert on how files are transferred on a computer network.
At first he didn't see any overlap between his and Gordon's work, but
inspiration would soon strike.

"The next day it occurred to me, 'Oh wait, this is almost the same as how
[Internet] protocols discover how much bandwidth is available for
transferring a file!'" Prabhakar said. "The algorithm the ants were using to
discover how much food there is available is essentially the same as that
used in the Transmission Control Protocol."

'anternet' discovered

Harvester ants. Creative commons photo: Steve Jurvetson (MS '89 Electrical
Engineering, MBA '95).

Transmission Control Protocol, or TCP, is an algorithm that manages data
congestion on the Internet, and as such was integral in allowing the early
web to scale up from a few dozen nodes to the billions in use today. Here's
how it works: As a source, A, transfers a file to a destination, B, the file
is broken into numbered packets. When B receives each packet, it sends an
acknowledgment, or an ack, to A, that the packet arrived.

This feedback loop allows TCP to run congestion avoidance: If acks return at
a slower rate than the data was sent out, that indicates that there is little
bandwidth available, and the source throttles data transmission down
accordingly. If acks return quickly, the source boosts its transmission
speed. The process determines how much bandwidth is available and throttles
data transmission accordingly.

It turns out that harvester ants (Pogonomyrmex barbatus) behave nearly the
same way when searching for food. Gordon has found that the rate at which
harvester ants – which forage for seeds as individuals – leave the nest to
search for food corresponds to food availability.

A forager won't return to the nest until it finds food. If seeds are
plentiful, foragers return faster, and more ants leave the nest to forage.
If, however, ants begin returning empty handed, the search is slowed, and
perhaps called off.

Prabhakar wrote an ant algorithm to predict foraging behavior depending on
the amount of food – i.e., bandwidth – available. Gordon's experiments
manipulate the rate of forager return. Working with Stanford student Katie
Dektar, they found that the TCP-influenced algorithm almost exactly matched
the ant behavior found in Gordon's experiments.

"Ants have discovered an algorithm that we know well, and they've been doing
it for millions of years," Prabhakar said.

They also found that the ants followed two other phases of TCP. One phase is
known as slow start, which describes how a source sends out a large wave of
packets at the beginning of a transmission to gauge bandwidth; similarly,
when the harvester ants begin foraging, they send out foragers to scope out
food availability before scaling up or down the rate of outgoing foragers.

Another protocol, called time-out, occurs when a data transfer link breaks or
is disrupted, and the source stops sending packets. Similarly, when foragers
are prevented from returning to the nest for more than 20 minutes, no more
foragers leave the nest.

Prabhakar said that had this discovery been made in the 1970s, before TCP was
written, harvester ants very well could have influenced the design of the

Gordon thinks that scientists have just scratched the surface for how ant
colony behavior could help us in the design of networked systems.

There are 11,000 species of ants, living in every habitat and dealing with
every type of ecological problem, Gordon said. "Ants have evolved ways of
doing things that we haven't thought up, but could apply in computer systems.
Computationally speaking, each ant has limited capabilities, but the
collective can perform complex tasks.

"So ant algorithms have to be simple, distributed and scalable – the very
qualities that we need in large engineered distributed systems," she said. "I
think as we start understanding more about how species of ants regulate their
behavior, we'll find many more useful applications for network algorithms."

The paper, "The Regulation of Ant Colony Foraging Activity without Spatial
Information," appears in the August 23 issue of PLoS Computational Biology.
tt mailing list

No comments:

Post a Comment