一类基于随机行走机理的优化路由改进策略

在对随机行走过程的研究中发现:单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积.据此,文章提出基于随机行走机理的优化路由改进策略.该策略以节点度连乘积最小化为原则,通过调节可变参数,建立节点处理能力均匀分布的情况下最佳路由策略.通过分析比较不同路由策略条件下平均路由介数中心度,网络的临界负载量,平均路径长度以及平均搜索信息量等性能指标,研究结果表明,此改进路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得最大幅度的提升. 关键词： 复杂网络 路由策略 负载传输     

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 ?.     

Traffic of packets with non-homogeneously selected destinations in scale-free network

In this paper, we study the information traffic flow in communication networks with scale-free topology. We consider the situation arising when packets are delivered to non-homogeneously selected destinations. It is found that the network capacity R_c increases with the increase of 〈k〉 (average degree of destination nodes) under local routing strategy. In contrast, R_c is essentially independent of 〈k〉 under shortest path strategy. Based on this finding, an integrated routing strategy that can enhance network capacity is proposed by combining the two strategies.     

Incremental routing strategy on scale-free networks

The most important function of a network is for transporting traffic. Due to the low traffic capacity of network systems under the global shortest path routing, plenty of heuristic routing strategies are emerging. In this paper, we propose a heuristic routing strategy called the incremental routing algorithm to improve the traffic capacity of complex networks. We divide the routing process into N$N$(the network size) steps and, at each step, we heuristically calculate all the routes for one source node considering both the dynamic efficient betweenness centrality and node degree information. We do extensive simulations on scale-free networks to confirm the effectiveness of the proposed incremental routing strategy. The simulation results show that the traffic capacity has been enhanced by a substantial factor at the expense of a slight lengthening in the average path.     

A dynamic routing strategy with limited buffer on scale-free network

In this paper, we propose an integrated routing strategy based on global static topologyinformation and local dynamic data packet queue lengths to improve the transmissionefficiency of scale-free networks. The proposed routing strategy is a combination of aglobal static routing strategy (based on the shortest path algorithm) and local dynamicqueue length management, in which, instead of using an infinite buffer, the queue lengthof each node i in the proposed routing strategy is limited by acritical queue length Q_ic. When the networktraffic is lower and the queue length of each node i is shorter than itscritical queue length Q_ic, it forwardspackets according to the global routing table. With increasing network traffic, when thebuffers of the nodes with higher degree are full, they do not receive packets due to theirlimited buffers and the packets have to be delivered to the nodes with lower degree. Theglobal static routing strategy can shorten the transmission time that it takes a packet toreach its destination, and the local limited queue length can balance the network traffic.The optimal critical queue lengths of nodes have been analysed. Simulation results showthat the proposed routing strategy can get better performance than that of the globalstatic strategy based on topology, and almost the same performance as that of the globaldynamic routing strategy with less complexity.     

Generalized minimum information path routing strategy on scale-free networks

This paper presents a new routing strategy by introducing a tunable parameter into the minimum information path routing strategy we proposed previously.It is found that network transmission capacity can be considerably enhanced by adjusting the parameter with various allocations of node capability for packet delivery.Moreover,the proposed routing strategy provides a traffic load distribution which can better match the allocation of node capability than that of traditional efficient routing strategies,leading to a network with improved transmission performance.This routing strategy,without deviating from the shortest-path routing strategy in the length of paths too much,produces improved performance indexes such as critical generating rate,average length of paths and average search information.     

Traffic resource allocation for complex networks

In this paper, an optimal resource allocation strategy is proposed to enhance traffic dynamics in complex networks. The network resources are the total node packet-delivering capacity and the total link bandwidth. An analytical method is developed to estimate the overall network capacity by using the concept of efficient betweenness (ratio of algorithmic betweenness and local processing capacity). Three network structures (scale-free, small-world, and random networks) and two typical routing protocols (shortest path protocol and efficient routing protocol) are adopted to demonstrate the performance of the proposed strategy. Our results show that the network capacity is reversely proportional to the average path length for a particular routing protocol and the shortest path protocol can achieve the largest network capacity when the proposed resource allocation strategy is adopted.     

无标度复杂网络负载传输优化策略

提出了一种能够显著提高无标度复杂网络负载传输性能的优化路由策略.实现了负载在核心节点与边缘节点间的合理分配.分析表明该策略使得网络的负载处理能力正比于网络规模的平方,而与单个节点的度值无关.实验结果显示优化路由策略在保持了最短路由策略小世界效应的同时,成倍地提升了网络的负载传输能力,且随着网络平均节点度的增加其优势越趋显著.此外,与有效路由策略的比较进一步验证了优化路由策略的优异性能. 关键词： 优化路由策略 复杂网络 负载传输 网络阻塞     

Adaptive local routing strategy on a scale-free network

Due to the heterogeneity of the structure on a scale-free network, making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult. In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination, an adaptive local routing strategy on a scale-free network is proposed, in which the node adjusts the forwarding probability with the dynamical traffic load (packet queue length) and the degree distribution of neighbouring nodes. The critical queue length of a node is set to be proportional to its degree, and the node with high degree has a larger critical queue length to store and forward more packets. When the queue length of a high degree node is shorter than its critical queue length, it has a higher probability to forward packets. After higher degree nodes are saturated (whose queue lengths are longer than their critical queue lengths), more packets will be delivered by the lower degree nodes around them. The adaptive local routing strategy increases the probability of a packet finding its destination quickly, and improves the transmission capacity on the scale-free network by reducing routing hops. The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.     

Bandwidth allocation strategy for traffic systems of scale-free network

In this Letter, the bandwidth resource allocation strategy is considered for traffic systems of complex networks. With a finite resource of bandwidth, an allocation strategy with preference parameter α is proposed considering the links importance. The performance of bandwidth allocation strategy is studied for the local routing protocol and the shortest path protocol. When important links are slightly favored in the bandwidth allocation, the system can achieve the optimal traffic performance for the two routing protocols. For the shortest path protocol, we also give a method to estimate the network traffic capacity theoretically.     

Probability routing strategy for scale-free networks

This study proposes a probability routing strategy for improving traffic capability on scale-free networks. Compared with the shortest path routing strategy depending on central nodes largely and the efficient routing strategy avoiding hub routers as much as possible, the probability routing strategy makes use of hub routers more efficiently, transferring approximate average amount of packs of the whole network. Simulation results indicate that the probability routing strategy has the highest network capacity among the three routing strategies. This strategy provides network capacity that can be more than 30 times higher than that of the shortest path routing strategy and over 50% higher than that of the efficient routing strategy. In addition, the average routing path length of our proposed strategy is over 10% shorter than that of the efficient routing strategy and only about 10% longer than that of the shortest path routing strategy.     

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.     

Optimization of transport protocols in complex networks

In this paper, an optimal routing strategy is proposed to enhance the traffic capacity of complex networks. In order to avoid nodes overloading, the new algorithm is derived on the basis of generalized betweenness centrality which gives an estimate of traffic handled by the node for a route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved, as our strategy, by redistributing traffic load from nodes with large betweenness centrality to nodes with small betweenness centrality in the proceeding of computing collective routing table. Particularly, depending on a parameter that controls the optimization scale, the new routing can not only enlarge traffic capacity of networks more, but also enhance traffic efficiency with smaller average path length. Comparing results of previous routing strategies, it is shown that the present improved routing performs more effectively.     

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.     

Empirical analysis of the worldwide maritime transportation network

In this paper we present an empirical study of the worldwide maritime transportation network (WMN) in which the nodes are ports and links are container liners connecting the ports. Using the different representations of network topology — the spaces L and P, we study the statistical properties of WMN including degree distribution, degree correlations, weight distribution, strength distribution, average shortest path length, line length distribution and centrality measures. We find that WMN is a small-world network with power law behavior. Important nodes are identified based on different centrality measures. Through analyzing weighted clustering coefficient and weighted average nearest neighbors degree, we reveal the hierarchy structure and rich-club phenomenon in the network.     

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.     

A maximum algebraic connectivity increment edge-based strategy for capacity enhancement in scale-free networks

In this paper, we focus on how to improve transportation efficiency of scale-free networks via edge increments. Based on analyzing the correlation between algebraic connectivity, which is the second smallest eigenvalue of the graph Laplacian matrix, and traffic capacity, we propose an effective edge-addition strategy called maximum algebraic connectivity increment edge (MACIE). Existing approaches are based on topological structure parameters, such as path and degree of a network, which require expensive computation. Different from existing edge-addition strategies, MACIE enhances transport efficiency by maximizing algebraic connectivity, and thus has a shorter running time. Simulation results show that MACIE is efficient and performs better than the previous strategy of reduction structural hole (RSH).     

Robustness analysis of static routing on networks

Robustness is one of the crucial properties that needs to be considered in the design of routing strategies on networks. We study the robustness of three typical routing strategies, which are the SP (shortest path), EP (efficient path), and OP (optimal path) strategies, by simulating several different kinds of attacks including random attacks, target attacks and cascading failures on scale-free networks. Results of the average path length, betweenness centrality, network capacity, etc., demonstrate that the EP strategy is more robust than the other two, and the OP strategy is more reliable than the SP strategy in general. However, on the power-grid network, the OP strategy is more resistant against cascading failures than the EP and SP strategies.     

一种应用于含权无标度网络的全局路由算法

针对含权无标度网络提出了一种全局路由算法.该算法利用网络路径上的节点强度信息构建了一种全局路由代价函数,选择使该代价函数最小的路径来传输信息包,有效避开了网络中易发生拥塞的核心节点.实验结果表明,与最短路径算法相比,该算法以较小的平均路径长度的增加为代价,将网络容量提高了十多倍.     

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.