Role of connectivity in congestion and decongestion in a communication network

We study network traffic dynamics in a two dimensional communication network with regular nodes and hubs. If the network experiences heavy message traffic, congestion occurs due to finite capacity of the nodes. We discuss strategies to manipulate hub capacity and hub connections to relieve congestion and define a coefficient of betweenness centrality (CBC), a direct measure of network traffic, which is useful for identifying hubs which are most likely to cause congestion. The addition of assortative connections to hubs of high CBC relieves congestion very efficiently. An erratum to this article is available at .     

基于复杂网络的交通拥堵与传播动力学分析

本文运用改进的中观交通流模型,研究了网络拓扑结构对交通拥堵的影响,进而分析复杂网络上的交通传播动力学特征和传播规律.结论有助于提出消除交通拥堵的有效控制策略以及交通规划的合理方案. 关键词： 复杂网络 交通流 交通拥堵 传播特性     

Assigning on-ramp flows to maximize highway capacity

In this paper, we study the capacity of a highway with two on-ramps by using a cellular automata traffic flow model. We investigate how to improve the system capacity by assigning traffic flow to the two ramps. The system phase diagram is presented and different regions are classified. It is shown that in region I, in which both ramps are in free flow and the main road upstream of the ramps is in congestion, assigning a higher proportion of the demand to the upstream on-ramp could improve the overall flow, which is consistent with previous studies. This is explained through studying the spatiotemporal patterns and analytical investigations. In contrast, optimal assignment has not been observed in other regions. We point out that our result is robust and model independent under certain conditions.     

Effects of decision-making on the transport costs across complex networks

We analyse the effects of agents’ decisions on the creation of congestion on a centralised network with ring-and-hub topology. We show that there are two classes of agents each displaying a distinct set of behaviours. The dynamics of the system are driven by an interplay between the formation of, and transition between, unique stable states that arise as the network is varied. We show how the flow of objects across the network can be understood in terms of the ordering and allocation of strategies. Our results show that the existence of congestion in a network is a dynamic process that is as much dependent on the agents’ decisions as it is on the structure of the network itself.     

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.     

Optimal traffic networks topology: A complex networks perspective

We investigate and analyse an optimal traffic network structure for resisting traffic congestion with different volumes of traffic. For this aim, we introduce a cost function and user-equilibrium assignment (UE) which ensures the flow balance on traffic systems. Our finding is that an optimal network is strongly dependent on the total system flow. And the random network is most desirable when the system flow is small. But for the larger volume of traffic, the network with power-law degree distribution is the optimal one. Further study indicates, for scale-free networks, that the degree distribution exponent has large effects on the congestion of traffic network. Therefore, the volume of traffic and characteristic of network determine the optimal network structure so as to minimize the side-effect produced by traffic congestion.     

Optimization in gradient networks

Gradient networks can be used to model the dominant structure of complex networks. Previous work has focused on random gradient networks. Here we study gradient networks that minimize jamming on substrate networks with scale-free and Erdos-Renyi structure. We introduce structural correlations and strongly reduce congestion occurring on the network by using a Monte Carlo optimization scheme. This optimization alters the degree distribution and other structural properties of the resulting gradient networks. These results are expected to be relevant for transport and other dynamical processes in real network systems.     

Biological evaluation of Trans-African highways

The Trans-African highway network is a unique concept of integrated development of transport corridors spanning all African countries and providing landlocked countries access to seaports. The planned road system is still maturing and just partially complete, thus giving us a chance to play with different scenarios of its growth and to consider potential alternative transport networks. We study the evolving transport network in the African continent with a groundbreaking technique of imitating growing transport networks with slime mould Physarum polycephalum. We represent the major urban areas of Africa with a source of nutrients, inoculate a piece of the slime mould in Cairo and allow the mould to span all urban areas with its network of protoplasmic tubes. We then compare the slime mould networks with existing and planned highway corridors. We found that slime mould provides a good approximation of the Trans-African highway network, with some roads of Eastern Africa delineated by P. polycephalum in a larger number of laboratory experiments. We demonstrate direct matches between protoplasmic tubes and Trans-Sahelian as well as Lagos-Mombasa corridors. Finally we analyse the bio-logic of transport network development in families of generalised Physarum graphs.     

Incident Detection Method of Expressway Based on Traffic Flow Simulation Model

The expressway traffic incidents have the characteristics of high harmful, strong destructive and refractory. Incident detection can guarantee smooth operation of the expressway, reduce traffic congestion and avoid secondary accident by informing the accident, detection and treatment timely. In this paper, an incident detection method is proposed using the toll station data that takes into account the traffic ratio at the entrances and crossway in the network. The expressway traffic simulation model is improved and a simulation algorithm is established to describe the movement of the vehicles. A numerical example is experimented on the expressway network of Shandong province. The proposed method can effectively detect the expressway incidents, and dynamically estimate the traffic network states so as to provide advice for the highway management department.     

Mitigation of congestion at a traffic bottleneck with diversion and lane restrictions

Mitigation of congestion on a two-lane highway with an off-ramp and an on-ramp is simulated with three-phase traffic theory. Advanced travel information-the average velocity of vehicles near the bottleneck at an on-ramp-is used to divert vehicles at an upstream off-ramp. If enough vehicles divert, previously expanding synchronous flow congestion can be stalled and isolated to the region between the ramps. The introduction of lane restrictions (forbidding lane changing on the portion of highway between the ramps) in addition to diversion substantially reduces and essentially eliminates the congestion, restoring flow to nearly free-flow conditions.     

Jamming in complex networks with degree correlation

We study the effects of the degree-degree correlations on the pressure congestion J when we apply a dynamical process on scale free complex networks using the gradient network approach. We find that the pressure congestion for disassortative (assortative) networks is lower (bigger) than the one for uncorrelated networks which allow us to affirm that disassortative networks enhance transport through them. This result agree with the fact that many real world transportation networks naturally evolve to this kind of correlation. We explain our results showing that for the disassortative case the clusters in the gradient network turn out to be as much elongated as possible, reducing the pressure congestion J and observing the opposite behavior for the assortative case. Finally we apply our model to real world networks, and the results agree with our theoretical model.     

互联网流量控制的朗之万模型及相变分析

为互联网中的流量控制协议构建恰当模型,从而阐明具体协议算法与网络宏观性能间的关系,一直是互联网研究者面临的重大挑战.本文通过逻辑演绎,建立了互联网传输控制协议下流量的朗之万方程.在此基础上,细致分析了主动队列管理算法的有效性,在理论上证明了此类算法存在从畅通态到拥塞态到瘫痪态的相变过程,并给出了相变临界点与系统参数的显式关系.本建模与分析方法虽以具体的主动队列管理算法为例,但其方法可以应用于一般的网络流量控制问题. 关键词： 互联网 流量控制 朗之万方程 相变     

一种新型结构光交叉连接节点及其联网性能分析

通过对常见光交叉连接器(OXC)的改进,提出了一种具有有限波长转换能力的内部光交叉连接节点(L-WIXC),既具备冲突消解能力又降低成本.采用算法编程方法,分析比较了L-WIXC和其他两种现有OXC结构,以及基于不同信令协议的L-WIXC的拥塞性能,结果表明L-WIXC具有较低的拥塞概率,并且基于JET协议的L-WIX...     

Networked analysis of the Shanghai subway network,in China

Recently, cities have become larger and larger, and more and more people are living in large cities. This phenomenon has caused serious traffic congestion which is very detrimental to the development of large cities. In this context, the subway has become the most effective solution for relieving traffic congestion and subways have been constructed in many cities, so the reliability and robustness of subways should be guaranteed. In this paper, Shanghai subway network, in China, will be analyzed and investigated; the topological characteristics and functional properties can be studied in order to assess the reliability and robustness. The topological characteristics can be measured using several parameters; meanwhile the fraction of removed nodes of Shanghai subway network is discussed and compared against that for a random network, and the critical threshold of this fraction is obtained. Two novel parameters called the functionality loss and connectivity of subway lines are proposed for measuring the transport functionality and the connectivity of subway lines. Subway lines 4 and 7 are selected as examples for evaluating the connectivity of lines subjected to different attack protocols. This study indicates that the subway network is robust against random attacks but fragile for malicious attacks, and the highest betweenness node-based attacks can cause the most serious damage to subway networks among the different attack protocols.     

Congestion analysis of traffic networks with direction-dependant heterogeneity

Traffic flow directionality and network weight asymmetry are widespread notions in traffic networks. This paper investigates the influence of direction-dependant heterogeneity on traffic congestion. To capture the effect of the link directionality and link weight asymmetry, the heterogeneity indexes of complex networks and the traffic flow model are introduced. The numerical results show that the critical value of heterogeneity determines congestion transition processes. The congestion degree increases with heterogeneity when the network heterogeneity is at a subcritical region. A network is more tolerant of congestion if the heterogeneity of the network is smaller or larger than the critical value. Furthermore, when heterogeneity reaches the critical value, the average number of accumulated vehicles arrives at the maximum and the traffic flow is under a serious congestion state. A significant improvement on the tolerance to congestion of traffic networks can be made if the network heterogeneity is controlled within a reasonable range.     

Impact of the Next-Nearest-Neighbor Interaction on Traffic Flow of Highway with Slopes

In this paper,we study the motion course of traffic flow on the slopes of a highway by applying a microscopic traffic model,which takes into account the next-nearest-neighbor interaction in an intelligent transportation system environment.Three common gradients of the highway,which are sag terrain,uphill terrain,and downhill terrain on a single-lane roadway,are selected to clarify the impact on the traffic flow by the next-nearest-neighbor interaction in relative velocity.We obtain the current-density relation for traffic flow on the sag,the uphill and the downhill under the next-nearest-neighbor interaction strategy.It is observed that the current saturates when the density is greater than a critical value and the current decreases when the density is greater than another critical value.When the density falls into the intermediate range between the two critical densities it is also found that the oscillatory jam,easily leads to traffic accidents,often appears in the downhill stage,and the next-nearest-neighbor interaction in relative velocity has a strong suppressing effect on this kind of dangerous congestion.A theoretical analysis is also presented to explain this important conclusion.     

Time-dependent collective behavior in a computer network model

The collective dynamics of large-scale computer networks remains elusive due to not only the internal adaptive behaviors of network-wide flows, but also the spatial–temporal changes in the external environment. In this paper, we investigate the time-dependent collective behavior by using a computer network model, recently developed to study space–time characteristics of congestion in large networks. We use the evolving correlation pattern, the largest eigenvalue, and the information entropy to analyze the macroscopic pattern of changing network congestion. We find the collective behavior becomes more pronounced during transient periods of pattern shifting, and the macroscopic pattern becomes gradually indistinct as the observed timescale increases to some extent. We also find that the evolving pattern of spatial–temporal correlation is more useful to reveal the time-dependent collective behavior of our model at different forcing levels.     

Self-organized criticality in a computer network model

We study the collective behavior of computer network nodes by using a cellular automaton model. The results show that when the load of network is constant, the throughputs and buffer contents of nodes are power-law distributed in both space and time. Also the feature of 1/f noise appears in the power spectrum of the change of the number of nodes that bear a fixed part of the system load. It can be seen as yet another example of self-organized criticality. Power-law decay in the distribution of buffer contents implies that heavy network congestion occurs with small probability. The temporal power-law distribution for throughput might be a reasonable explanation for the observed self-similarity in computer network traffic.     

Research on the search ability of Brownian particles on networks with an adaptive mechanism

In this paper, we focus on the search ability of Brownian particles with an adaptive mechanism. In the adaptive mechanism, nodes are allowed to be able to change their own accepting probability according to their congestion states. Two searching-traffic models, the static one in which nodes have fixed accepting probability to the incoming particles and the adaptive one in which nodes have adaptive accepting probability to the incoming particles are presented for testing the adaptive mechanism. Instead of number of hops, we use the traveling time, which includes not only the number of hops for a particle to jump from the source node to the destination but also the time that the particle stays in the queues of nodes, to evaluate the search ability of Brownian particles. We apply two models to different networks. The experiment results show that the adaptive mechanism can decrease the network congestion and the traveling time of the first arriving particle. Furthermore, we investigate the influence of network topologies on the congestion of networks by addressing several main properties: degree distribution, average path length, and clustering coefficient. We show the reason why random topologies are more able to deal with congested traffic states than others. We also propose an absorption strategy to deal with the additional Brownian particles in networks. The experiment results on Barabási–Albert (BA) scale-free networks show that the absorption strategy can increase the probability of a successful search and decrease the average per-node particles overhead for our models.     

基于引力约束的复杂网络拥塞问题研究

如何在保证网络传输效率的同时提高网络的吞吐量是目前研究的主要问题. 通过研究节点对数据包传递过程的引力作用,提出了一种具有引力约束的路由算法. 为检验算法的有效性,通过引入一个状态参数H, 利用由稳态到拥塞状态的指标流量相变值来度量网络的吞吐量, 同时利用数据包的最大传输时间〈T_max〉 与平均传输时间 〈T_avg〉来分析网络的传输效率. 针对算法在不同引力约束条件下的路由情况进行了仿真.仿真结果表明, 若数据传递过程只考虑路径长度最短,则会导致网络吞吐量较低且流量分布极不均匀; 若只顾及等待时间最短,会导致传输路径过度迂回且大部分节点都会陷入拥塞状态; 同时考虑路径长度和等待时间的引力作用并选取适当引力的节点进行传递, 可以显著提高网络吞吐量并缓解网络的拥塞程度.