自适应随机化链路状态路由算法

目前使用的两种IP路由算法－距离矢量和链路状态，都基于局域最优思想：每个路由器为其转发的包选择某种距离测试下的最短路径尽力发送，但是由于网络业务量具有无特征尺度的突发性，带宽资源经常可能处于相对稀缺的临界状态，在这种情况下，基于局域最优的路由策略通常并不对应于全局的最优，一个明显的例子是由局域最优算法所导致的路由振荡，提出的自适应随机化链路状态路由算法利用自适应随机化方法协调，限制各路由器的局域最优要求，有效地解决了路由振荡问题，仿真表明新算法显著提高了以包平均传输延迟和包丢失率为测度的网络的整体传输性能，此外，新算法的协调机制仍是局域性的，因而不显著地增加通信和计算开销。

A SELF-ADAPTIVELY RANDOMIZED LOOP-FREE ROUTING ALGORITHM

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.