Analysis Of Congestions And Routing Strategies Of Complex Networks

Since the seminal work on scale-free networks by Barabasi and Albert and on the small-world phenomenon by Watts and Strogatz, the structure and dynamics of complex networks have recently attracted a tremendous amount of interest and attention from the scholars in all fields. Congestion phenomenon is a typical dynamical process which takes place on complex networks such as communication network and traffic network. The increasing importance of large communication networks such as the Internet, upon which our society survives, calls for the need for high efficiency in handling and delivering information. In this light, to find optimal strategies for traffic routing is one of the important issues we have to address. On the base of summarizing and concluding previous research results about congestion and optimized routing strategy, the issue of congestion and routing strategy are studied for a variety of complex network model. Several improved routing strategies are proposed in order to increase the network capacity and optimize the transportation performance.The main contents and contributions of this dissertation are summarized as follows.1. We numerically investigate the effectiveness of the traffic awareness routing strategy for scale-free networks with different clustering. Compared with the shortest path routing protocol, the network capacity is greatly enhanced by the traffic awareness routing strategy and the emergence of congestion is delayed. We also find that there exists an optimum value for the tunable parameter in the congestion awareness strategy. Moreover, simulation results show that the more clustered network, the less efficient the packet delivery process.2. By the traffic awareness routing strategy, we investigate the influence of complex networks topological structure on the traffic delivery. Here we address influence of the topology on the dynamics of traffic flow for complex networks, taking into account the network topology, the information generating rate, and the information-processing capacity of individual nodes. Based on the different delivery capacity of each node, we present three kinds of traffic models. Moreover, the critical value is obviously different for different topological structures and dynamic process. 3. Since global information is usually unavailable in large-scale networks, several local routing strategies are proposed based on local topological and dynamic information for enhancing the efficiency of traffic delivery on scale-free networks. In order to characterize the efficiency of the packet delivery process, we introduce an order parameter to measure the network capacity by the critical value of phase transition from free flow to congestion. Simulation results show that the capacity of maximum traffic flow is greatly enhanced by the optimal controlled parameter in three kinds of routing strategies. To explain the effects of traffic flow on congestion, we study the simulations of packets distribution on each node in the different state.4. We propose another new routing strategy based on the local topological information and the estimated waiting time in scale-free network. According to the new routing strategy with a single tunable parameter, a packet is delivered to next node with probability that depends not only on the degree of the next node but also the estimated waiting time at the node. The routing algorithm is implemented in BA scale-free networks in the case of node delivering ability proportional to its degree. Simulations show that the maximal network capacity corresponds to an optimal controlled parameter.5. We propose an evolutionary model for weighted network with tunable clustering coefficient according to characteristics of real network. The model gives power-law distributions of degree, weight, and strength, as confirmed in many real networks. In particular, the weighted model has a nonlinear correlation between average clustering coefficient and degree, which is in good agreement with flat head real weighted technological networks. The effect of the weighted network structure on traffic delivery is investigated. The packet traffic flow on the weighted scale-free networks is investigated based on the local routing strategy using node strength, and the delivering ability of node is controlled by node strength. It is shown by simulations that the traffic dynamics depend strongly on the controlled parameter.