Routing strategies in traffic network and phase transition in network traffic flow

The dynamics of information traffic over scale-free networks has been investigated systematically. A series of routing strategies of data packets have been proposed, including the local routing strategy, the next-nearest-neighbour routing strategy, and the mixed routing strategy based on local static and dynamic information. The capacity of the network can be quantified by the phase transition from free flow state to congestion state. The optimal parameter values of each model leading to the highest efficiency of scale-free networked traffic systems have been found. Moreover, we have found hysteretic loop in networked traffic systems with finite packets delivering ability. Such hysteretic loop indicates the existence of the bi-stable state in the traffic dynamics over scale-free networks.      

Information traffic in scale-free networks with fluctuations in packet generation rate

We study the information traffic in scale-free networks where the information generation rate varies with time as a periodic function. We observe that when the fluctuation in packet generation rate increases, the average transit time increases and network performance degrades. In order to improve the transportation efficiency in this situation, we propose a new routing method called mixed routing. It operates in two modes: (1) when the packet generation rate is small, the shortest paths are used to deliver the packets to the destination; (2) when the packet generation rate is large, the traffic loads in central nodes are redistributed to other non-central nodes, using the so-called efficient routing method. We find that the time shifting between the two modes is very critical for the routing performance. Consequently, we provide an efficient method to determine the critical times to shift the routing modes for achieving good network performance.     

Traffic dynamics based on a traffic awareness routing strategy on scale-free networks

By incorporating local traffic information into the shortest path routing strategy, we numerically investigate the effectiveness of the traffic awareness routing strategy for scale-free networks with different clustering. In order to characterize the efficiency of the packet-delivery process, we introduce an order parameter and an average transmission time that allow us to measure the network capacity by the critical value of phase transition from free flow to congestion. Compared with the shortest path routing protocol, the network capacity is greatly enhanced by the traffic awareness routing strategy. 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 the network, the less efficient the packet-delivery process.     

The effect of TTL on the information traffic

In real communication protocols, the information packets have a finite Time-to-Live (TTL) to avoid the waste of network resources, such as infinite loop induced by routing error or too long transferring time. In this paper, we introduce TTL into the information traffic model on Barabási-Albert scale-free networks under local routing strategy and focus on its effect on the network capacity measured by the critical point (R_c) of phase transition from free flow to congestion. Simulations show that the network capacity and the communication velocity are improved. However, some packets are dropped before they arrived at destinations. It is found that the share of successfully arrived packets monotonously increases with the increment of TTL and it is considerably acceptable if TTL is not very small. We also examine the effect of TTL on the positive-feedback preference (PFP) internet model and the results are alike. Our work may be helpful in quantifying the effect of packet lifetime in real communication networks and in routing strategy designing.     

Improved routing strategy based on gravitational field theory

Routing and path selection are crucial for many communication and logistic applications. We study the interaction between nodes and packets and establish a simple model for describing the attraction of the node to the packet in transmission process by using the gravitational field theory, considering the real and potential congestion of the nodes. On the basis of this model, we propose a gravitational field routing strategy that considers the attractions of all of the nodes on the travel path to the packet. In order to illustrate the efficiency of proposed routing algorithm, we introduce the order parameter to measure the throughput of the network by the critical value of phase transition from a free flow phase to a congested phase,and study the distribution of betweenness centrality and traffic jam. Simulations show that, compared with the shortest path routing strategy, the gravitational field routing strategy considerably enhances the throughput of the network and balances the traffic load, and nearly all of the nodes are used efficiently.     

基于感知流量算法的复杂网络拥塞问题研究

研究了在具有感知流量的路由策略下,复杂网络的拓扑结构对网络中传输流量的影响.为了描述数据包传输过程的有效性,通过引入一个状态参数,利用由稳态到拥塞的指标流量相变值来刻画网络的吞吐量.基于每个节点的数据包处理能力与该节点的度或介数成比例提出两种模型并进行仿真.仿真结果表明,平均度相同的情况下,模型Ⅰ中,WS小世界网络比ER随机网络和BA无标度网络更容易产生拥塞;模型Ⅱ中,所有网络容量都得到较大的提高,尤其是WS小世界网络.但当网络的基本连接参数改变时,哪种模型更利于网络的流量传输,还要依据网络本身的结构特性 关键词： 复杂网络 无标度网络 感知流量 拥塞     

Detrended Fluctuation Analysis of Traffic Data

Different routing strategies may result in different behaviour of traffic on internet. We analyse the correlation of traffic data for three typical routing strategies by the detrended fluctuation analysis （DFA） and lind that the aregree of correlation of the data can be divided into three regions, i.e. weak, medium, and strong correlation. The DFA scalings are constants in both the regions of weak and strong correlations but monotonically increase in the region of medium correlation. We suggest that it is better to consider the traffic on complex network as three phases, i.e. the free, buffer, and congestion phase, than just as two phases believed before, i.e. the free and congestion phase.     

Major impact of queue-rule choice on the performance of dynamic networks with limited buffer size

We investigate the similarities and differences among three queue rules, the first-in-first-out(FIFO) rule, last-in-firstout(LIFO) rule and random-in-random-out(RIRO) rule, on dynamical networks with limited buffer size. In our network model, nodes move at each time step. Packets are transmitted by an adaptive routing strategy, combining Euclidean distance and node load by a tunable parameter. Because of this routing strategy, at the initial stage of increasing buffer size, the network density will increase, and the packet loss rate will decrease. Packet loss and traffic congestion occur by these three rules, but nodes keep unblocked and lose no packet in a larger buffer size range on the RIRO rule networks. If packets are lost and traffic congestion occurs, different dynamic characteristics are shown by these three queue rules. Moreover, a phenomenon similar to Braess' paradox is also found by the LIFO rule and the RIRO rule.     

Integrating network structure and dynamic information for better routing strategy on scale-free networks

We study information packet routing processes on scale-free networks by mimicking the Internet traffic delivery strategies. We incorporate both the global network structure information and local queuing information in the dynamic processes. We propose several new routing strategies to guide the packet routing. The performance of the routing strategies is measured by the average transit time of the packets as well as their dependence on the traffic amount. We find that the routing strategies which integrate both global network structure information and local dynamic information perform much better than the traditional shortest-path routing protocol which takes into account only the global topological information. Moreover, from comparative studies of these routing strategies, we observe that some of our proposed methods can decrease the average transit time of packets but the performance is closely dependent on the total amount of traffic while some other proposed methods can have good performance independent of the total amount of traffic with hyper-excellent average transit time of packets. Also, numerical results show that our proposed methods integrating network structure information and local dynamic information can work much better than the methods recently proposed in [S. Sreenivasan, R. Cohen, E. López, Z. Toroczkai, H.E. Stanley, Phys. Rev. E 75 (2007) 036105, Zhi-Xi Wu, Gang Peng, Eric W.M. Wong, Kai-Hau Yeung, J. Stat. Mech. (2008) P11002.], which only considered network structure information.     

Efficient routing on small complex networks without buffers

In this paper, we are exploring strategies for the reduction of the congestion in the complex networks. The nodes without buffers are considered, so, if the congestion occurs, the information packets will be dropped. The focus is on the efficient routing. The routing strategies are compared using two generic models, i.e., Barabàsi–Albert scale-free network and scale-free network on lattice, and the academic router networks of the Netherlands and France. We propose a dynamic deflection routing algorithm which automatically extends path of the packet before it arrives at congested node. The simulation results indicate that the dynamic routing strategy can further reduce the number of dropped packets in a combination with the efficient path routing proposed by Yan et al. [5].     

The Effect of Queueing Strategy on Network Traffic

In recent years, the transportation system has been faced by increasing challenge in congestion and inefficiency, and research in traffic network has become a significant area of interest. In this paper, we introduce a dynamic-information-based (DIB) queueing strategy into network traffic model under the efficient routing strategy. DIB makes a packet with higher priority to be delivered if there are less packets travelling along its path from the current node to the destination. It is found that, compared with the traditional first-in-first-out (FIFO) queueing strategy, DIB can effectively balance the traffic load of the system via delaying packets to be delivered to congested nodes. Although the network capacity has no obvious changes, some other indexes which reflect transportation efficiency are efficiently improved in the congestion state. Besides, extensive simulation results and discussions are provided to explain the phenomena. The results may provide novel insights for research on traffic systems.     

Traffic dynamics in scale-free networks with tunable strength of community structure

In this paper we systematically investigate the impact of community structure on traffic dynamics in scale-free networks based on local routing strategy. A growth model is introduced to construct scale-free networks with tunable strength of community structure, and a packet routing strategy with a parameter α is used to deal with the navigation and transportation of packets simultaneously. Simulations show that the maximal network capacity stands at α=−1 in the case of identical vertex capacity and monotonously decreases with the strength of community structure which suggests that the networks with fuzzy community structure (i.e., community strength is weak) are more efficient in delivering packets than those with pronounced community structure. To explain these results, the distribution of packets of each vertex is carefully studied. Our results indicate that the moderate strength of community structure is more convenient for the information transfer of real complex systems.     

Deterministic weighted scale-free small-world networks

We propose a deterministic weighted scale-free small-world model for considering pseudofractal web with the co-evolution of topology and weight. Considering the fluctuations in traffic flow constitute a main reason for congestion of packet delivery and poor performance of communication networks, we suggest a recursive algorithm to generate the network, which restricts the traffic fluctuations on it effectively during the evolutionary process. We provide a relatively complete view of topological structure and weight dynamics characteristics of the networks such as weight and strength distribution, degree correlations, average clustering coefficient and degree-cluster correlations as well as the diameter.     

Dynamics of congestion transition triggered by multiple walkers on complex networks

The congestion transition triggered by multiple walkers walking along the shortest path on complex networks is numerically investigated. These networks are composed of nodes that have a finite capacity in analogy to the buffer memory of a computer. It is found that a transition from free-flow phase to congestion phase occurs at a critical walker density f_c, which varies for complex networks with different topological structures. The dynamic pictures of congestion for networks with different topological structures show that congestion on scale-free networks is a percolation process of congestion clusters, while the dynamics of congestion transition on non-scale-free networks is mainly a process of nucleation.     

Efficient packet routing strategy in complex networks

We investigate a new efficient packet routing strategy which mitigates traffic congestion on complex networks. In order to avoid congestion, we minimize the maximum betweenness, which is a measure for concentration of routing paths passing through a node in the network. Danila et al. propose a packet routing strategy in which, instead of shortest paths, they used efficient paths, which are the paths with the minimum total summations of weights assigned to nodes in the respective paths. They use a heuristic algorithm in which the weights are updated step by step by using the information of betweenness of each node in every step and the respective total summations of weights for paths through the nodes with large degrees become comparatively large. Thus passage through such nodes, where congestion almost occurs, is likely to be avoided in their algorithm. The convergence time by their algorithm is, however, quite long. In this paper, we propose a new efficient heuristic algorithm which balances traffic on networks by achieving minimization of the maximum betweenness in the much smaller number of iteration steps for convergence than that by the algorithm of Danila et al.     

Optimal structure of complex networks for minimizing traffic congestion

To design complex networks to minimize traffic congestion, it is necessary to understand how traffic flow depends on network structure. We study data packet flow on complex networks, where the packet delivery capacity of each node is not fixed. The optimal configuration of capacities to minimize traffic congestion is derived and the critical packet generating rate is determined, below which the network is at a free flow state but above which congestion occurs. Our analysis reveals a direct relation between network topology and traffic flow. Optimal network structure, free of traffic congestion, should have two features: uniform distribution of load over all nodes and small network diameter. This finding is confirmed by numerical simulations. Our analysis also makes it possible to theoretically compare the congestion conditions for different types of complex networks. In particular, we find that network with low critical generating rate is more susceptible to congestion. The comparison has been made on the following complex-network topologies: random, scale-free, and regular.     

Global forward-predicting dynamic routing for traffic concurrency space stereo multi-layer scale-free network

Many real communication networks, such as oceanic monitoring network and land environment observation network,can be described as space stereo multi-layer structure, and the traffic in these networks is concurrent. Understanding how traffic dynamics depend on these real communication networks and finding an effective routing strategy that can fit the circumstance of traffic concurrency and enhance the network performance are necessary. In this light, we propose a traffic model for space stereo multi-layer complex network and introduce two kinds of global forward-predicting dynamic routing strategies, global forward-predicting hybrid minimum queue(HMQ) routing strategy and global forward-predicting hybrid minimum degree and queue(HMDQ) routing strategy, for traffic concurrency space stereo multi-layer scale-free networks. By applying forward-predicting strategy, the proposed routing strategies achieve better performances in traffic concurrency space stereo multi-layer scale-free networks. Compared with the efficient routing strategy and global dynamic routing strategy, HMDQ and HMQ routing strategies can optimize the traffic distribution, alleviate the number of congested packets effectively and reach much higher network capacity.     

Traffic dynamics in scale-free networks with limited packet-delivering capacity

We propose a limited packet-delivering capacity model for traffic dynamics in scale-free networks. In this model, the total node’s packet-delivering capacity is fixed, and the allocation of packet-delivering capacity on node i is proportional to , where k_i is the degree of node i and ? is a adjustable parameter. We have applied this model on the shortest path routing strategy as well as the local routing strategy, and found that there exists an optimal value of parameter ? leading to the maximal network capacity under both routing strategies. We provide some explanations for the emergence of optimal ?.     

Dynamics of traffic networks: From microscopic and macroscopic perspectives

Considering the microscopic characteristics (vehicle speed, road length etc.) of links and macroscopic behaviors of traffic systems, we derive the critical flow generation rate in scale-free networks. And the dynamics of traffic congestion is studied numerically in this paper. It is shown that the queue length increases with microscopic characteristics of links. Additionally, the critical flow generation rate decreases with increase of the network size N, maximum speed v_max and parameter τ. The significance of this finding is that, in order to improve the traffic environment, both the local information for the single link and behaviors of the whole network must be analyzed simultaneously in a traffic system design.     

基于节点相关性的网络不动点理论研究

现代复杂的通信网络内部存在着广泛的幂律现象，网络节点之间存在相关特性. 根据这种相关特性，提出了网络不动点理论. 将Banach不动点理论引入网络模型，证明了网络不动点理论的正确有效性. 证明过程是把通信网络看作由路径预测算法产生的似马尔可夫链的路由节点迭代序列形成的网络空间. 由节点相关性可知，此空间中的节点序列相对越长就越能折射出搜索的目标所在，预测准确率也会逐步增加，可以更好地进行目标定位、数据挖掘等. 通过某种路由准则的算子从源节点最终映射到的目的节点与Banach空间的不动点相对应，即为网络空间的不动点. 当网络发展到能为用户提供真正的无处不在的连接时，网络不动点理论的物理特性将非常明显. 因为网络规模越大，节点间的群体作用越显著，就越能显现网络不动点理论的物理特性. 关键词： 计算机网络 长程相关 不动点 幂律