【作者】 田铭；

【导师】 兰巨龙；

【作者基本信息】 解放军信息工程大学 ， 通信与信息系统， 2010， 硕士

【摘要】 传统IP路由协议中最短路径优先的路由模式容易导致较短路径上产生拥塞,而其它链路相对空闲。因此,在传统路由模式下,加强路由的控制能力,实现流量均衡分配成为路由优化算法研究的重点之一。论文针对目前网络的传输拥塞问题,结合国家863计划探索导向课题“一种基于节点势能导向的多路由产生机制”的研究进展,立足于现有IP网络数据单下一跳转发的普遍情况,提出并研究了基于网络整体流量均衡的路由多选一优化方案。首先对最短路径优先(OSPF)协议中存在等价多路径可选的情况进行了分析和优化;进而将可选下一跳链路集合进行扩充,研究多下一跳路由机制下的优化算法;最后给出多下一跳路由的在线切换算法,达到负载均衡,避免突发流量引起的拥塞。概括起来,主要工作如下:1.提出一种基于链路关键度的等价多路径路由优化算法LCER。该算法通过链路关键度表征链路在网络中的平均任务负载,在等价路径之间选择平均任务负载最轻的路径,使得各节点对之间的路由冲突最小化的同时,也避免了报文乱序。仿真表明LCER算法比随机选择算法和分流算法降低了“热点”链路的竞争,在吞吐量、报文保序、平均时延等方面性能也有所提高。2.提出了基于距离和链路关键度的多下一跳路由优化算法DLCR。该算法在提供所有可行下一跳资源的前提下,具有较短路径和较低链路关键度的下一跳链路将被优先选择,从而降低了网络资源消耗,避免了路由冲突。仿真表明该算法避免了路径在“热点”链路的竞争,为接纳更多路径请求,保障服务质量创造了条件,改善了丢包率和吞吐量性能。算法参数可根据优化目标的不同灵活进行设置。3.设计了一种基于流量均衡的多下一跳路由切换算法TBMS。该算法针对突发流量可能引起的部分链路拥塞问题,利用多下一跳路由机制丰富的候选路径集合,在链路利用率达到触发条件时,及时切换到其它路径,避免了链路过载产生的拥塞。由于对切换时机进行了严格定义,可达到较好的报文保序性能,同时避免了频繁切换路径出现路由振荡。仿真结果表明,该方案在获得良好的丢包率和吞吐量性能的同时,链路利用率的均衡性相对DLCR算法也有所改善。更多还原

【Abstract】 The shortest-path-first routing mode in traditional IP routing protocols easily leads to create congestion in the hot-spot links, and relatively leisure of other links. Therefore, based on the traditional route, strengthening the control ability of routing algorithms, to balance the distribution of traffic is one focus of the routing optimization problem study.Combined with the national 863 project―a multi-next-hop routing mechanism based on node potential orientation‖, this dissertation analyzed the existing technologies of traffic balancing, and then proposed route optimization problem strategy. The Equal-Cost-Multi-Path in OSPF protocol which has multiple paths, is optimized firstly; then the candidate path set was extended, and the routing optimization problem under the Multi-next-hop routing mechanism was studied. At last a routing switching algorithm to avoid the routing congestion of links was proposed. To sum up, the main work is as follows:1. A link-criticality-based ECMP routing algorithm, named LCER, was proposed. The algorithm selected a specific path with relatively light average load to forward the traffic, according to the task in the network, so as to minimize the interference between the node pairs. Single path forwarding avoids the out of order problem caused by multi-path forwarding. Simulation results show that LCER algorithm could aviod the interference on the hots-pot links, achieve better performance of throughput, average delay and packet in order than random selection and traffic splitting algorithm.2. Combined with the optimization objective of reducing the network consumption and avoiding the interference between the routing requests this paper proposed a multi-next-hop routing algorithm based on distance-and-link-criticality, named DLCR. Simulation results show that the algorithm could achieve better performance in decrease packet-loss-ratio, and increase network throughput, and played a certain role in avoiding interference because the utilization of hot link was decreased than other algorithms. Parameter can be set flexibly according to different optimization objectives.3. An online routing switching algorithm is designed to avoid the link congestion. This algorithm was a complement of DLCR. To avoid route oscillation caused by frequent routing switch and serious out of order problem caused by traffic splitting, the strategy of the algorithm made strict definition of switching time. The analysis demonstrated that under the premise of that the message length is greater than the maximum of all path delay difference, the receiver can avoid out of order problem. Simulation results show that the algorithm could mitigate packet loss caused by competition of network resources, significantly increased network throughput, and made a markedly improvement on the distribution of the network traffic, compared with the DLCR algorithm.更多还原