Rollback Traffic Avoidance for Snapshot routing algorithm in cyclic mobile networks

In this paper, we propose an offline rollback traffic avoidance method for the snapshot routing in cyclic mobile networks. Since the snapshot routing tables are switched simultaneously, part of the traffic may be sent back on some links if the new routing path contains the same links but with reversed forwarding direction against the old one. To avoid the rollback traffic, we first formulate the rollback traffic avoidance problem as an integer programming problem which is NP-hard, and then we propose an approximate algorithm called Inter-Snapshot Rollback Traffic Avoidance (ISRTA), to pursuit the approximate optimal solutions. Simulation results show that our method can efficiently eliminate the rollback paths and traffic in the Iridium system. Although the global average network delay is increased slightly, the extra end to end delay caused by rollback traffic is eliminated and the packet loss rate is reduced.