Akira Kataoka, ATR Laboratories, Kyoto, Japan
We have enhanced AntNet's adaptability, enabling it to respond in real
time to changing network conditions. The routing probability of
AntNet is equal to the probability that a neighboring node be selected
as the next hop node. Since AntNet is based on a positive feedback
mechanism, even if one of the agents selects a neighboring node as the
next hop node and experiences a long trip time, the routing
probability corresponding to the neighboring node does not decrease.
A routing probability decreases only if other routing probabilities
for the same destination increase. If a routing probability is
approximately one, it will be hard to decrease, since almost all of
the agents select the neighboring node corresponding to that routing
probability. We call this phenomenon routing-lock. Routing-lock
lengthens the time from the moment a network event (e.g., a network
topology change) occurs to the moment AntNet's routing shifts to a new
shortest path routing. To counter this, we propose two lock-free
algorithms. One is a decay method and the other is a negative
feedback method. The former reduces the rate of routing-locked
probabilities and the latter quickly performs unlocking, immediately
after the occurrence of a network event. Accordingly, a lock-free
Antnet is an Antnet algorithm that uses one of the two lock-free
algorithms. We show how lock-free AntNets can suppress the growth of
the number of packets in a network after the occurrence of a network
event.