Study Of Routing Strategy On Scale-free Network

Recent studies indicate that many complex networks such as the Internet, powergrids, urban road networks are not homogeneous similar to random and regularnetworks, but heterogeneous with degree distribution following the power-lawdistribution. All these networks play an extremely important role in our daily life,but there also exists the congestion problem generally. As a result, how to alleviatetraffic congestion and enhance network capacity have become a research focus.Optimizing routing strategy is an economic and simple way to improve networkperformance compared to many other methods. Therefore, the study of routingstrategy on a scale-free network is of great practical significance, and worthy offurther study. This thesis mainly focuses on routing strategy. The primarycontributions are listed as follows:1) According to different types, many routing strategies on complex networksare discussed. On one hand, traditional routing strategies such as breadth-firstrouting and random walk routing are introduced briefly; on the other hand,theoptimized routing strategies based on global information and local information areanalyzed in details, and their respective characteristics and applicable environmentsare summarized. The significance of this study is to provide a useful reference forthe design and selection of routing strategy.2) A new routing strategy with a tunable parameter α is proposed. It is based onthe nodes’ delivering ability and queue information of a scale-free network. Thenetwork capacity is analyzed by using critical generation rate. The queue length ofeach node is assumed to be unlimited and the FIFO (first in first out) discipline isapplied at each queue, and PIA (path iteration avoidance) rule will be obeyed whenthe packets are delivered. Considering the existence of different handling anddelivering ability of nodes, we assume that the node with larger degree has strongerdelivering ability, making it proportional to the degree of the node. Simulationshows that the system’s capacity can be enhanced maximally when α=3. Moreover,we also study how the critical point Rcis affected by the link density of the BAnetwork, results indicate that increasing link density enhances the capacity of the BAnetwork obviously. Finally, we compare the improved routing strategy with thetraditional one which is based on local topological information. It is shown that thenew one performs more effectively. Furthermore, the average path length of the improved routing strategy is shorter than the traditional one when the packagegeneration rate is relatively low or high.3) The impact of nodes characteristics on the routing strategy is discussed.Firstly, two kinds of node capacity model are introduced. In the first model, thedelivering ability of nodes is constant, but proportional to the degree in the secondmodel. Secondly, the situation of special node failure is investigated. Simulationshows that the routing strategy based on dynamic information is more robust than theone based on static information, when using the second model. However, in the firstmodel, the network performance with the nodes of low degree partial failure is betterthan the few high degree nodes does, but there exists a severer congestion when thenetwork packet generation rate reaches to a certain level.