Lock-free AntNets and their Adaptability Evaluations

Kazumasa Oida, ATR Laboratories, Kyoto, Japan
Email: oida@acr.atr.co.jp

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.