Research On Load Balancing Algorithm Based On Multi-next Hop Routing Mechanism

Based on the single path forwarding routing mechanism, Packets only have one output port, the contention of the same port between several packets is congestion-proneness, and directly deteriorate the performance of the whole network. Combined with the national 863 project―fast self-healing routing protocol and test system‖, this dissertation is devoted to propose load splitting algorithm which not only can enhance the performance of balancing but also keep packet in-order. Therefore this algorithm can use the network bandwidth effectively and provide better quality of services to users.The main work of this dissertation is outlined as follows:1. The performance of typical load balancing algorithms is researched on balancing and packet in-order performances. The simulation results of two balancing algorithms under different link conditions show that reordering packets will greatly reduce TCP's performance. This two typical load balancing algorithm can not keep the balancing and packet in-ordering simultaneously. Because of the fact that packets have multiple selected output port in the multi-next hop routing scheme, a load balancing algorithm is required, which can keep packet in-order. 2. Aiming at the heavy-tailed distribution of flow size, a dynamic load balancing algorithm TDLB is proposed. When the load splitting is imbalanced, TDLB can decreases the remapping numbers and reduces the probability of reordering packets by only remapping aggressive flows. The results of simulation show that the TDLB can enhance the performance of keeping packet in-order while satisfying the balancing demand. 3. According to time-lag feature of the traffic burst character, this dissertation presents a dynamic load balancing algorithm (FCLB) based on the flow chopping mechanism. The results of researching on placing balls model in theory reveal that the balancing performance is directly proportional to the numbers of the traffic unit, while is inversely proportional to the coefficient of variation. FCLB splits traffic into segments as the basic traffic splitting unit by using the flow chopped mechanism, which can keep packets in-order. The balancing performance is improved remarkably by the fine granularity. Simulation results show that FCLB can keep the performances of balancing and packet in-ordering ideally. 4. According to the requirements of project, the dissertation introduces a project implement scheme of FCLB on the network processor nP3450. The nP3450 simulation results reveal that the scheme can not only satisfied the requirements of project but also easy to be expanded.