On the
surface, ants and the Internet don’t seem to have much in common. But two
Stanford University 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 says. “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.”
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—for example, 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 says.
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 min, no more foragers
leave the nest.
Prabhakar
says that had this discovery been made in the 1970s, before TCP was written,
harvester ants very well could have influenced the design of the Internet.
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 says. “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 says. “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 work is published
in PLoS Computational Biology.
Source: Stanford University
