摘要
自适应路由算法能够根据网络状态选择能回避阻塞或故障结点的路径 ,使得链路得到有效利用 ,均匀分布通信流量 ,减少平均传输延时 ,最大限度地提高网络的性能 .该文针对一种结构简单、易于实现、性能较优的多跳虚拟环网结构 DS- WDM Ring设计了三种自适应路由算法 .在 PC机上设计并实现了路由算法模拟模型 ,对 DS-WDM Ring上的自适应路由算法和静态路由算法进行了模拟 ,统计出了几种路由算法在不同的网络负载下的平均阻塞率、平均跳数、平均延时和结点端口的利用率 ,比较分析了几种路由的性能 .
Three adaptive routing algorithms called FDR (Forward Deflection Routing), FUUR (Farthest Unused Routing), and DR (Deflection Routing) are presented in this paper for DS WDM Ring. The FDR algorithm tries to keep the hops number minimum or near minimum while reducing the blocking probability. The principle of FDR is that if the virtual ring selected at the very beginning is busy, other virtual rings with a shorter step length would be tried in order. The FUUR algorithm attempts to reduce the blocking probability further by balancing the packet traffic. This algorithm selects the port that is unused for the longest period of time among all ports with a step length shorter than or equal to the distance to the destination node. The DR algorithm further reduces the blocking probability of FDR. In FDR, if ports with a step length shorter than the distance to destination node are all busy, the packet would be blocked. While in the DR routing algorithm, the virtual ring with a step length larger than the distance to destination node will be selected. In this case, the packet would skip over its destination node in order to reach the destination within the next loop. A simulation model is designed for analyzing the performance of these routing algorithms. The metrics includes expecting blocking probability, average hops number, average transmission delay, and the port utilization. Under this model, the performance of these adaptive routing algorithms are analyzed and compared with that of the static routing algorithm LSOR. The results of simulation show that the expecting blocking probability of FDR and DR are lower than that of FUUR and LSOR, the average hops of FDR is less than that of FUUR and DR, the average transmission delay of FDR is shorter than that of FUUR and DR. The ports are utilized uniformly in FDR. The FUUR is designed to balance the loads among channels with a hope to get the lowest blocking probability. Actually, FUUR does not win its goal because more packets are transmitted through the paths with a smaller step length. This makes the average hop number increase considerably. With the packet arrival rate unchanged, the effect is equivalent to increasing the actual load, so the blocking probability increases. Authors conclude that the FDR is most suitable to the DS WDM Ring.
出处
《计算机学报》
EI
CSCD
北大核心
2002年第7期778-783,共6页
Chinese Journal of Computers
基金
国家"八六三"高技术研究发展计划 (863 -3 0 6-ZD11-0 1-8)
教育部留学回国基金资助