Analysis And Optimization Strategies Of Traffic Capacity Of Complex Networks

Since the discovery of Small-World phenomenon by Watts and Strogatz in1998and Scale-Free property by Barabasi and Albert in1999, the research on complex networks has entered a period of rapid development. It has been a hot topic that most real networks can be modeled by complex networks and the analysis methods for complex networks can be practiced in analyzing real networks recently at home and abroad. One key function of network is to transport objects running on it, such as data packets on the Internet, and vehicles in highway networks. Traffic capacity is employed to measure the transportation ability of network. In recent years, with ever-growing number of users and massive data transmission, traffic congestion occurs on current networks more frequently. Studies about reducing network congestion and enhancing traffic capacity of complex systems have become the focus. Three essential ingredients influencing traffic capacity are routing algorithm, network structure including topology and resource distributions, and traffic model which indicates the dynamics and behaviors of traffic flow and is strongly related to the analysis of traffic capacity. In realistic complex networks, network resources such as node’s delivery capacity, link’s bandwidth and queue resource are finite and non-uniformly distributed, and substantially restrict the network performance. This thesis mainly focuses on routing strategy, and two aspects of network structure:network topology and link’s bandwidth allocation strategies.(1) On the issue of optimizing routing strategy, considering the betweenness of node as the factor of routing cost function, in this thesis we introduce one betweenness-based efficient routing strategy; based on the consideration of traffic congestion occurring on links of many real networks, a link congestion based weighted routing strategy in which the edge betweenness is regarded as factor of routing cost is investigated; decomposing the routing process into N(the network size) steps, at each step, the dynamic congestion information based on the existing routing table is employed, and we call such routing process as incremental routing(IR); in order to resolve the routing flaps for the destination-based global dynamic routing strategy and to simplify the functions of routers, a vector switching based global dynamic routing mechanism is presented and we adopt it in near real complex network models and evaluate its effects on network traffic capacity. One dynamic source routing strategy on two-level flow traffic model is presented to support different packet’s transmission needs in real complex systems such as the Internet.(2) On the issue of optimizing network topology, firstly, to develop the whole transport efficiency of network by adding a fraction of edges into network, four edge addition strategies are discussed in total, and we investigate the network traffic capacity, load balance, average shortest path length and robustness of different network models. Secondly, six edge rewiring strategies are reported, and expanded discussions are done subsequently. Thirdly, one two-layer network model is studied to enhance the whole network traffic capacity by using link-removal method on the upper layer network. Extensive simulations have been done to confirm the effectiveness of these strategies, and their possible applications are also discussed.(3) On the issue of link’s bandwidth allocation, with finite total links’bandwidth resource, two bandwidth allocation strategies are considered:betweenness based link’s bandwidth allocation strategy and the global dynamic bandwidth allocation strategy. Both theoretical analysis and extensive simulations verify that good link’s bandwidth allocation mechanism can strongly improve the traffic capacity of network.This thesis carries out in-depth study of the ingredients affecting the network traffic capacity and ten strategies are proposed to ameliorate the network traffic capacity with corresponding simulations and theoretical analysis. These strategies will provide basic suggestions for promoting the transport efficiency of network or network planning.