Abstract: Current IP routing algorithms, such as distance vector （DV） and link state （LS）, are based on the thought of local optimization: every router tries its best to transfer the packets in the shortest path. Because of scale-free bursts of network load, bandwidth is often critical resources. In this case, routing algorithms based on local optimization might lead to a severe disadvantage: routing oscillation, which will remarkably depress global performances. A novel self-adaptively randomized loop-free link state （ARLS） algorithm is proposed, which utilizes local information to achieve self-adaptive randomization and harmonize each router’s local performance requests. ARLS can effectively eliminate routing oscillation phenomena and improve global performance of communication networks. Computer simulation demonstrates that ARLS can gain a prominent superiority in average queueing delay and packet loss rate over basic LS. The work, as a real example, implies that dynamic components of a complex system that could not be exactly modeled by mathematic models may result in a stable status of inferior performance with a considerable probability, and proper randomization can help system get rid of the inferior status rapidly.