# Traffic Dynamics on Complex Networks: A Survey

Authors: Shengyong Chen; Wei Huang; Carlo Cattani; Giuseppe Altieri
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Traffic dynamics on complex networks are intriguing in recent years due to their practical implications in real communication networks. In this survey, we give a brief review of studies on traffic routing dynamics on complex networks. Strategies for improving transport efficiency, including designing efficient routing strategies and making appropriate adjustments to the underlying network structure, are introduced in this survey. Finally, a few open problems are discussed in this survey.


---

## Body

## 1. Introduction

Large real communication networked systems have become a hot research topic for a rather long time. Typical examples include the Internet, which is an enormous network of many routers connected by physical or wireless links with information packets flowing on them, and high-way network, which is composed of cities and high-ways between cities. The rapid development of society causes the immense increase of traffic amounts in many real networked communication systems. Congestion may firstly occur on some communication units (such as routers on the Internet [1, 2] or cities in high-way networks) and then spread to more other units. Therefore, it is important to recover the free-flow state from the congested state, and therefore, demands for high transport efficiency are becoming more stringent in recent years. Up till now, there have been many studies on understanding and controlling traffic congestion on communication systems [3–18]. However, many early studies only assumed that the communication networked systems are completely random or even ignored the existence of network structure. Since the pioneering discovery of small-world phenomena [19] and scale-free feature [20, 21] at the end of 20th century, researchers began to realize that traffic dynamics are highly relevant to the underlying network structure. For example, in 2005, Zhao et al. found that for two networks with different network structures, even when the two networks have the same average connectivity, the same delivering capacity of each node, and the same number of nodes, traffic congestion may tend to occur in one network than in another [22]. Therefore, traffic dynamics on complex network have attracted a lot of interest in both applied physics and computational science.Actually, many empirical studies have revealed that the transport performances are not only relevant to the characteristics of underlying network structure, but also significantly affected by routing strategies. In this light, in order to improve transport performances on real networks, one can either design efficient routing strategies, or make appropriate changes to the underlying network structure. Designing efficient routing strategies is considered to be “soft” strategies, because it does not require any topological changes. Making changes to network structure is considered to be “hard” strategies, because it requires topological changes. One can add a few links to existing networks or delete a few links from existing networks to realize the modification of network structure.In this survey, we mainly review recent progresses for traffic dynamics on complex networks. We have to mention that this survey is mainly from the perspective of physics. The remainder of this survey is organized as follows. In Section2, we introduce some basic models and concepts for traffic routing dynamics. In Sections 3 and 4, we present some important work on “soft” strategies and “hard” strategies, respectively. Finally, conclusions are drawn in Section 5 with a brief discussion for future work.


## 2. Models and Concepts for Traffic Dynamics

### 2.1. Traffic Routing Model

Processes of random walk on complex networks have been extensively studied recently due to its wide applications in real networks [19, 23, 24]. However, the accumulation of packets on routers is not involved in the process of random walk, and therefore, the process of random walk cannot reflect real traffic system completely. Under the background of complex network, a basic traffic dynamics model has been proposed and frequently used to mimic the traffic transport in communication networked systems [7, 22, 25–27]. In this basic model, all nodes in a network are equally considered as hosts and routers [26, 28] for generating and delivering packets. The whole traffic dynamics model is an iterated process. In a general setting, packets are generated with a give rate ρ at randomly selected nodes at each time step. Each packet is designated with a randomly chosen node, different from its source, as the destination to which the packet will be delivered. Each packet is delivered from one node to another following a given routing strategy. Each node has its own delivering capacity C, that is, the maximal number of packets each node can deliver at one time step. An arrived packet will be placed at the end of the queue if this node already has some packets to be delivered to their respective destinations. The packets in queue, which may be created locally at some previous time steps or they are delivered by other nodes in an earlier time, work on a “first-in-first-out” basis. Finally, a packet will be removed from the network once it reaches its destination.The basic model has also been generalized to more realistic models, which incorporate the fact that hub nodes usually have high delivering capacities or can generate more packets at each unit time step than those low-degree nodes can do. For example, degree-dependent delivering capacity was assumed in the form1+kiθ [29] or 1+βki [22, 30]. In [30, 31], the author assumed that degree-dependent packet generation rate in the form λki. In [32, 33], the authors assumed that the bandwidth B of each link, that is, the maximal capacity of each link for delivering packets, is limited and varies from link to link. Moreover, in [34], the authors assumed that sources and destinations are not homogeneously selected. They considered two situations of packet generation: (i) packets are more likely generated at high-degree nodes and (ii) packets are more likely generated at low-degree nodes. Similarly, they considered two situations of packet destination: (a) packets are more likely to go to high-degree nodes and (b) packets are more likely to go to low-degree nodes.


### 2.2. Traffic Capacity

One of the most important measurements for transport performance of traffic is the traffic capacityρc, that is, the critical packet generation rate. At ρc, the network undergoes a phase transition from free-flow state to congested state. When the packet generation rate ρ is below ρc, the number of generated and delivered packets are balanced, and therefore, the network is in free-flow state. But when ρ goes beyond ρc, the number of packets keeps on increasing with time and can lead to congestion finally, simply because nodes cannot delivering too many packets at each time step due to limited delivering capacity. The traffic capacity is usually described by an order parameter [6](2.1)η(ρ)=lim⁡t→∞⁡C〈ΔW〉ρNΔt,
where 〈ΔW〉=W(t+1)-W(t) and 〈⋯〉, the average over time windows of width Δt. W(t) is denoted as the number of packets in the network, and N is the network size. When ρ<ρc, ΔW=0, and η=0, this indicates that the network system is under the free-flow state. On the other hand, when ρ>ρc, η is above zero, which indicates that packets are accumulating in the network and the network will become congested. Thus, ρc is the maximal packet generation rate under which the network system can remain in the free-flow state.


### 2.3. Effective Betweenness

In order to provide a theoretical estimate of traffic capacity, the concept “betweenness” is introduced here. Betweenness centrality [35–38], or betweenness for short, measures how central a node is in the network. Originally, the betweenness of a node l is defined as the number of total shortest paths that pass through the node l. Let σij(l) be the number of paths going through node l and following the shortest paths between node i and node j. The node betweenness, Bl, can be expressed as Bl=∑ijσij(l), where i,j≠l. Later on, the definition of node betweenness was extended. The path between any two distinct nodes may not be along the shortest path between the two nodes but is guided by a given searching algorithm. This is the so-called effective node betweenness [26, 39]. When the searching algorithm is able to find the shortest path between any two distinct nodes, the effective node betweenness recovers the original definition of node betweenness [35–38]. The effective node betweenness can be defined as [26, 39](2.2)Bj=∑i,mbijm,
where bijm is the average times that a packet generated at i and with destination m that passes through j. In a network with N nodes, we define(2.3)bm=(b11m…b1Nm⋮⋱⋮bN1m⋯bNNm).
According to [26, 39], (2.4)bm=(I-pm)-1pm,
where I is an identity matrix and (2.5)pm=(p11m…p1Nm⋮⋱⋮pN1m⋯pNNm),
where pijm is the probability that a packet whose destination points to node m goes from node i to a new node j in the next movement. Under the transportation rule regulated, from [26, 39], we have(2.6)pijm=aimδjm+(1-aim-δim)Pi→j,m=aimδjm+(1-aim-δim)k̃jαd̃j,mβ∑l∈Nei(i)k̃lαd̃l,kβ,
where aim is the element in the adjacency matrix of the network (aim=1 if there is a direct edge between node i and node m; otherwise, aim=0) and δjm is the delta function. It should be noted that pmjm=0 for all j, which means that a packet will be removed from the network when it reaches its destination, and pimm=1 for all i≠m, which means a packet will be directly forwarded to the destination node m if node m is a direct neighbor of node i.Then, we can make a theoretical estimate for the traffic capacityρc. The number of packets that arrive at node i is, on average, ρBi/(N-1). If ρBi/(N-1)>C, packets will be accumulated on the node i, and congestion will thereafter occur. To avoid congestion on the network, ρBi/(N-1)≤C should hold for each node. Therefore, the traffic capacity can be estimated as [22, 26](2.7)ρc=C(N-1)Bmax⁡,
where Bmax is the maximal effective betweenness in the network.


## 2.1. Traffic Routing Model

Processes of random walk on complex networks have been extensively studied recently due to its wide applications in real networks [19, 23, 24]. However, the accumulation of packets on routers is not involved in the process of random walk, and therefore, the process of random walk cannot reflect real traffic system completely. Under the background of complex network, a basic traffic dynamics model has been proposed and frequently used to mimic the traffic transport in communication networked systems [7, 22, 25–27]. In this basic model, all nodes in a network are equally considered as hosts and routers [26, 28] for generating and delivering packets. The whole traffic dynamics model is an iterated process. In a general setting, packets are generated with a give rate ρ at randomly selected nodes at each time step. Each packet is designated with a randomly chosen node, different from its source, as the destination to which the packet will be delivered. Each packet is delivered from one node to another following a given routing strategy. Each node has its own delivering capacity C, that is, the maximal number of packets each node can deliver at one time step. An arrived packet will be placed at the end of the queue if this node already has some packets to be delivered to their respective destinations. The packets in queue, which may be created locally at some previous time steps or they are delivered by other nodes in an earlier time, work on a “first-in-first-out” basis. Finally, a packet will be removed from the network once it reaches its destination.The basic model has also been generalized to more realistic models, which incorporate the fact that hub nodes usually have high delivering capacities or can generate more packets at each unit time step than those low-degree nodes can do. For example, degree-dependent delivering capacity was assumed in the form1+kiθ [29] or 1+βki [22, 30]. In [30, 31], the author assumed that degree-dependent packet generation rate in the form λki. In [32, 33], the authors assumed that the bandwidth B of each link, that is, the maximal capacity of each link for delivering packets, is limited and varies from link to link. Moreover, in [34], the authors assumed that sources and destinations are not homogeneously selected. They considered two situations of packet generation: (i) packets are more likely generated at high-degree nodes and (ii) packets are more likely generated at low-degree nodes. Similarly, they considered two situations of packet destination: (a) packets are more likely to go to high-degree nodes and (b) packets are more likely to go to low-degree nodes.


## 2.2. Traffic Capacity

One of the most important measurements for transport performance of traffic is the traffic capacityρc, that is, the critical packet generation rate. At ρc, the network undergoes a phase transition from free-flow state to congested state. When the packet generation rate ρ is below ρc, the number of generated and delivered packets are balanced, and therefore, the network is in free-flow state. But when ρ goes beyond ρc, the number of packets keeps on increasing with time and can lead to congestion finally, simply because nodes cannot delivering too many packets at each time step due to limited delivering capacity. The traffic capacity is usually described by an order parameter [6](2.1)η(ρ)=lim⁡t→∞⁡C〈ΔW〉ρNΔt,
where 〈ΔW〉=W(t+1)-W(t) and 〈⋯〉, the average over time windows of width Δt. W(t) is denoted as the number of packets in the network, and N is the network size. When ρ<ρc, ΔW=0, and η=0, this indicates that the network system is under the free-flow state. On the other hand, when ρ>ρc, η is above zero, which indicates that packets are accumulating in the network and the network will become congested. Thus, ρc is the maximal packet generation rate under which the network system can remain in the free-flow state.


## 2.3. Effective Betweenness

In order to provide a theoretical estimate of traffic capacity, the concept “betweenness” is introduced here. Betweenness centrality [35–38], or betweenness for short, measures how central a node is in the network. Originally, the betweenness of a node l is defined as the number of total shortest paths that pass through the node l. Let σij(l) be the number of paths going through node l and following the shortest paths between node i and node j. The node betweenness, Bl, can be expressed as Bl=∑ijσij(l), where i,j≠l. Later on, the definition of node betweenness was extended. The path between any two distinct nodes may not be along the shortest path between the two nodes but is guided by a given searching algorithm. This is the so-called effective node betweenness [26, 39]. When the searching algorithm is able to find the shortest path between any two distinct nodes, the effective node betweenness recovers the original definition of node betweenness [35–38]. The effective node betweenness can be defined as [26, 39](2.2)Bj=∑i,mbijm,
where bijm is the average times that a packet generated at i and with destination m that passes through j. In a network with N nodes, we define(2.3)bm=(b11m…b1Nm⋮⋱⋮bN1m⋯bNNm).
According to [26, 39], (2.4)bm=(I-pm)-1pm,
where I is an identity matrix and (2.5)pm=(p11m…p1Nm⋮⋱⋮pN1m⋯pNNm),
where pijm is the probability that a packet whose destination points to node m goes from node i to a new node j in the next movement. Under the transportation rule regulated, from [26, 39], we have(2.6)pijm=aimδjm+(1-aim-δim)Pi→j,m=aimδjm+(1-aim-δim)k̃jαd̃j,mβ∑l∈Nei(i)k̃lαd̃l,kβ,
where aim is the element in the adjacency matrix of the network (aim=1 if there is a direct edge between node i and node m; otherwise, aim=0) and δjm is the delta function. It should be noted that pmjm=0 for all j, which means that a packet will be removed from the network when it reaches its destination, and pimm=1 for all i≠m, which means a packet will be directly forwarded to the destination node m if node m is a direct neighbor of node i.Then, we can make a theoretical estimate for the traffic capacityρc. The number of packets that arrive at node i is, on average, ρBi/(N-1). If ρBi/(N-1)>C, packets will be accumulated on the node i, and congestion will thereafter occur. To avoid congestion on the network, ρBi/(N-1)≤C should hold for each node. Therefore, the traffic capacity can be estimated as [22, 26](2.7)ρc=C(N-1)Bmax⁡,
where Bmax is the maximal effective betweenness in the network.


## 3. “Soft” Strategies

### 3.1. Shortest Path Routing Strategy

Under the shortest path routing strategy, each packet is always transported along the topological shortest path between the packet’s source and destination. Different from routing strategies with stochastic factors, under the shortest path routing strategy, each packet has a fixed delivering path once the network is constructed. Therefore, the shortest path routing strategy is widely used in real communication systems [2, 40–42] due to its economical and technical costs. However, under the shortest path routing strategy, packets are easy to pass through hub nodes, which can easily lead to congestions on hub nodes [29, 43, 44]. This fact consequently motivates the designing of many other efficient routing strategies, which will be introduced in the following part.


### 3.2. Review of Improved Routing Strategies for Traffic Dynamics

It has been demonstrated that networks cannot handle heavy traffic if packets are always transported along the shortest path from source and destination [29, 43, 44]. To improve transport efficiency of packets in the network, Echenique et al. proposed a strategy in [45, 46], called traffic-awareness strategy, in which the factor of waiting time at the neighboring nodes is also considered in addition to the fact of shortest path length from the neighboring node to destination. The waiting time is regarded as the number of packets in the queue at a neighboring node at the time of decision [45, 46]. The authors investigated the maximal time 〈Tmax〉 it takes for a packet to travel from its source to destination and the traffic capacity ρc in complex heterogeneous networks. Results show that compared to the shortest path routing strategy, 〈Tmax〉 is shortened and ρc is enhanced by using the traffic-awareness strategy. Moreover, in [46], the authors mentioned that under the shortest path routing strategy, traffic jams appear and grow smoothly, as the amount of generated packets increases. However, as soon as traffic awareness conditions are taken into account, the jamming transition is reminiscent of a first-order phase transition. Therefore, we can say that traffic-awareness routing strategy can delay the appearance of congestion at the cost of a sudden jump to a highly jammed phase due to the lack of early warnings.Later on, Zhang et al. in [30] proposed an efficient routing strategy that is based on the projected waiting time along the shortest path from a neighboring node to the destination. Figure 1 illustrates the comparing results of three routing strategies in heterogeneous complex networks. λ and β are parameters related to degree-dependent packet generation rate and degree-dependent packet delivering capacity. Results show that jamming is harder to occur using the strategy in [30], when compared with both the shortest path strategy and traffic-awareness strategy [45, 46]. The strategy in [30] has the advantage of spreading the packets among the nodes according to the degree of nodes.Figure 1
The critical valueβc(λ) for three different routing strategies: the strategy proposed in [30] (circles), traffic-awareness strategy [45, 46] with h=0.8 (stars) and the shortest path strategy (squares). The lines are guides to eye.In [29], the authors incorporated both the global shortest path length information and local degree information in the transport process of traffic, via two tunable parameters, α and β, to guide the routing of packets. In detail, at each time step, all packets move from their current position, i, to the next node in their path, j, with a probability Qij defined as (3.1)Qij=kjαexp⁡⁡[-β(dit-djt-1)]∑l∈Ωiklαexp⁡⁡[-β(dit-dlt-1)],
where Ωi is the set of neighboring nodes of i, kj is the degree of node j, and dit is the shortest path length between node i and node t. The parameters α and β are tunable parameters with varying range α∈(-∞,∞) and β∈[0,∞). Through numerical simulations, the authors in [29] showed that with appropriate selection of the tunable parameters, the strategy in [29] is superior to the shortest path routing strategy in enhancing the traffic capacity. Furthermore, the authors of [29] pointed out that the strategy in [45, 46] is sensitive to the total number of tasks assigned to the networks. In the case of heavy traffic, the contribution of shortest path length for delivering packets can be ignored, because the diameter of most real communication networks grows only logarithmically with system size [1] and shortest path length is only bound to the diameter value. However, the strategy in [29] is insensitive to the amount of traffic flow in the network. In [39], based on the strategy which considered both shortest path length ingredient and degree ingredient in heterogeneous networks, the authors proposed an improved routing strategy with memory information in scale-free networks. This result was inspired by [47], in which researchers found that when studying local search in power-law communication networks, the search efficiency can be effectively enhanced if retracing the last step is disallowed in random networks. In the strategy with memory information [39], when node A receives a new packet from node B, node A has to record that the new packet is from node B. At the next time step, the packet node A is forbidden to be forwarded back to node B. In this way, the chance that packets are transported back and forth between two distinct nodes is greatly reduced. Figure 2 shows the results of performances in enhancing traffic capacity for both strategies with and without memory information. In Figure 2, α regulates the degree ingredient involved for forwarding packets, and β regulates the shortest path length ingredient involved for forwarding packets. γ denotes the degree exponent of scale-free networks. Results show that traffic capacity can be effectively enhanced by using the strategy with memory information.(a) The traffic capacity rateρc versus the degree exponent γ with β equal to 1. The cases of α=-1, 0, and 1 are marked with asterisks, circles, and squares, respectively. (b) The traffic capacity ρc versus α. The cases of γ=3, 2.5, and 2 are marked with asterisks, circles, and squares, respectively. In both figures, dotted and solid lines are for the routing strategies with and without memory information. Network size is set to 500 in both figures [39].
(a)(b)In [44], the authors proposed a kind of efficient routing strategy. In order to find the optimal routing strategy, the authors define “the efficient path.” For any path between node i and node j as P(i→j):=i≡x0,x1,...,xn-1,xn≡j, define (3.2)L(P(i⟶j):β)=∑i=0n-1k(xi)β,
where k(xi) is the degree of node xi and β is a tunable parameter. The efficient path between i and j is corresponding to the route that makes the sum L(P(i→j):β) minimal. It is obvious that L(β=0) recovers the shortest path routing strategy. It is expected that the system behaves better under the routing rule with β>0 than under the shortest path routing strategy. In [44], the authors concerns how Rc [28], that is, the critical number of generated packets at each time step, varies with β. Here, Rc=Nρc. The simulation results for the critical value Rc as a function of β on BA scale-free networks are illustrated in Figure 3. It can be found that Rc firstly increases with β and then decreases, with the maximal Rc corresponding to β=1. As compared to the shortest path routing strategy (β=0), the traffic capacity is greatly improved, from Rc≈4 when β=0 to Rc≈45 when β=1, more than ten times. However, the authors also found that the average total delivering path length is maximal when β=1. Therefore, they concluded that the system capability in processing information is considerably enhanced at the cost of increasing the average total delivering path length when using the strategy [30].Figure 3
The criticalRc versus β for scale-free networks with size N=1225. Both simulations and theoretical analysis indicate that the maximal value of Rc corresponding to β≈1. The data shown here is the average over 10 independent runs [44].The routing strategies mentioned above, allow each node to have the whole network’s global topological information, which may be practical for small or medium size networks but not for large real communication such as the Internet, WWW [48], peer-to-peer networks [25, 49], or urban transportation system [50, 51]. However, strategies based on local information (each node only knows the information of its neighbors) are favored in large networks due to heavy communication cost on searching global information in networks. Inspired by the study on network search or network navigation on complex networks [47, 52–55], the authors in [56, 57] present a traffic model in which packets are routed only based on local topological information with a single tunable parameter α. The optimized value of α was sought out to maximize the traffic capacity. In this model, each node performs a local search among its neighbors. If the packet’s destination is within the searched area, it is delivered directly to its destination. Otherwise, it is forwarded to a node i, one of the neighbors of the searching node, according to the preferential probability(3.3)Πi=kiα∑jkjα,
where the sum runs over all neighbors of the searing node i, ki is the degree of node i, and α is a tunable parameter. With the delivering capacity of each node set as a constant C, the simulation results show that the optimal performance of the system corresponds to α=-1, which can be observed from Figure 4. Theoretical analyses for the optimal value α=-1 were obtained in [56]. The authors of [56] also pointed out that choosing the optimal α=-1 not only maximizes the traffic capacity but also minimizes the average delivering time. When the delivering capacity of each node is proportional to its degree k, the optimal value of α changes to α=0, as demonstrated in Figure 5. This result indicates that under the conditions of heterogeneous delivering capacity of each node, the random walks strategy is the best choice for routing packets.Figure 4
CriticalRc versus α on a BA scale-free network with network size N=1000 and constant delivery capacity of each node C=10. The maximal of Rc corresponds to α=-1 marked by a dotted line [56].Figure 5
The critical generating rateRc versus α in the case of delivery capacity of each node proportional to its degree Ci=ki. Here, kmin is set to be 3 and network size N=1000. The maximum of Rc corresponds to α=0 marked by a dotted line [56].Actually, the area of information that each router can access can significantly affect the performances of local routing strategy in traffic transport on complex networks. References [58, 59] found that the next-to-nearest routing algorithm can perform much better than the nearest routing algorithm under the random routing strategy. The next-to-near routing algorithm means that a packet can directly be delivered to its destination if the destination is one of the next-to-nearest neighbors of the searching node.The strategy in [56, 57] is only based on local static information, which can only enhance the traffic capacity but cannot considerably reduce the transport time. In [49], the authors proposed a new routing strategy based on local static and dynamical information in scale-free networks. In the routing model of [49], it was assumed that each node has an identical delivering capacity C. A packet is directly delivered to its destination if the destination is one of the direct neighbors of the searing node l. Otherwise, the probability of a neighbor node i to which the packet will be delivered is(3.4)Pl→i=ki(ni+1)β∑jkj(nj+1)β,
where the sum runs over all neighbors of the searching node i, ni is the number of packets in the queue of i and β is a tunable parameter. Also, this model considers the effect of transmission delay on the traffic dynamics. The delay is defined as the number of time steps in receiving updated dynamical information from the neighbors [49]. Figure 6 shows that in the case of no delay, the traffic capacity is considerably reduced when decreasing β until β≈-3. The maximal traffic capacity is only 23 when choosing C=5 under the case of only adopting local topological information [56, 57]. Results show that the traffic capacity is further improved by using the strategy in [49] as compared to the strategy in [56, 57]. The average transport time 〈T〉 is reported in Figure 7. It can be seen that by adopting the strategy in [56, 57], 〈T〉 is approximately independent of R. When R is not too large, 〈T〉 is much shorter by adopting the strategy in [49] than the strategy in [56, 57]. In real communication system, the local dynamical information can be obtained by using the keep-alive messages that router continuously exchange with their peers [45].Figure 6
The network capacityRc versus parameter β for different time delay and for different network size N. The other parameter is C=5 [49].Figure 7
Average transport time〈T〉 versus R for strategies in [49, 56, 57], respectively. α=-1 corresponds to the optimal value of the strategy in [56, 57] and β is the parameter of the strategy in [49]. The network size is set to N=1000 and the node delivering capacity is set to C=5.In [60], the authors proposed another global routing strategy which considers both global topological information and queue length of each node. In this global strategy, the packets are delivered along the path in which the sum of queue length of nodes is a minimum. The path between node i (source) and node j (destination) can be denoted as(3.5)Pij=min⁡⁡∑m=0l[1+n(xm)],
where n(xm) is the queue length of node and l is the path length. Figures 8(a)–8(c) show the evolution of the total packet number Np under the shortest path strategy [29, 43, 44], the efficient strategy proposed in [44], and the global dynamic paths with the network size N=500 and average degree 〈k〉=4. Figure 8(d) compares the relation of order parameter η versus R under the three routing strategies. It can be seen that the traffic capacity under the shortest path strategy [29, 43, 44] is Rc=3. The efficient strategy in [44] has Rc=20 and the global dynamic strategy can reach up to Rc=41. Therefore, the global dynamic strategy can achieve the highest traffic capacity.Evolution in the packet number in the network under different routing strategies [60]. (a) Shortest path routing strategy, (b) Efficient routing strategy in [44], and (c) The global dynamic routing strategy. (d) The order parameter η versus R under the three routing strategies.
(a)(b)(c)(d)Figure9 shows the relation of traffic capacity Rc versus the average degree 〈k〉 and versus the network size N under the three routing strategies [60]. Results show that the traffic capacity under the global dynamic routing strategy is the largest. Because the node queue length changes from time to time, it is computationally time consuming to find the global paths at each time step. Therefore, the authors in [60] introduced a time delay δT for the update of the global queue information and the corresponding paths. They found that with the increment of time delay, the traffic capacity remains almost the same, but the total packet number in system, the traveling time, and the waiting time will increase.(a) The traffic capacityRc versus average degree 〈k〉 with the same network size N=500 under the three routing strategies. (b) The traffic capacity Rc versus the network size N with the same average degree 〈k〉=4 under the three routing strategies [60].
(a)(b)


## 3.1. Shortest Path Routing Strategy

Under the shortest path routing strategy, each packet is always transported along the topological shortest path between the packet’s source and destination. Different from routing strategies with stochastic factors, under the shortest path routing strategy, each packet has a fixed delivering path once the network is constructed. Therefore, the shortest path routing strategy is widely used in real communication systems [2, 40–42] due to its economical and technical costs. However, under the shortest path routing strategy, packets are easy to pass through hub nodes, which can easily lead to congestions on hub nodes [29, 43, 44]. This fact consequently motivates the designing of many other efficient routing strategies, which will be introduced in the following part.


## 3.2. Review of Improved Routing Strategies for Traffic Dynamics

It has been demonstrated that networks cannot handle heavy traffic if packets are always transported along the shortest path from source and destination [29, 43, 44]. To improve transport efficiency of packets in the network, Echenique et al. proposed a strategy in [45, 46], called traffic-awareness strategy, in which the factor of waiting time at the neighboring nodes is also considered in addition to the fact of shortest path length from the neighboring node to destination. The waiting time is regarded as the number of packets in the queue at a neighboring node at the time of decision [45, 46]. The authors investigated the maximal time 〈Tmax〉 it takes for a packet to travel from its source to destination and the traffic capacity ρc in complex heterogeneous networks. Results show that compared to the shortest path routing strategy, 〈Tmax〉 is shortened and ρc is enhanced by using the traffic-awareness strategy. Moreover, in [46], the authors mentioned that under the shortest path routing strategy, traffic jams appear and grow smoothly, as the amount of generated packets increases. However, as soon as traffic awareness conditions are taken into account, the jamming transition is reminiscent of a first-order phase transition. Therefore, we can say that traffic-awareness routing strategy can delay the appearance of congestion at the cost of a sudden jump to a highly jammed phase due to the lack of early warnings.Later on, Zhang et al. in [30] proposed an efficient routing strategy that is based on the projected waiting time along the shortest path from a neighboring node to the destination. Figure 1 illustrates the comparing results of three routing strategies in heterogeneous complex networks. λ and β are parameters related to degree-dependent packet generation rate and degree-dependent packet delivering capacity. Results show that jamming is harder to occur using the strategy in [30], when compared with both the shortest path strategy and traffic-awareness strategy [45, 46]. The strategy in [30] has the advantage of spreading the packets among the nodes according to the degree of nodes.Figure 1
The critical valueβc(λ) for three different routing strategies: the strategy proposed in [30] (circles), traffic-awareness strategy [45, 46] with h=0.8 (stars) and the shortest path strategy (squares). The lines are guides to eye.In [29], the authors incorporated both the global shortest path length information and local degree information in the transport process of traffic, via two tunable parameters, α and β, to guide the routing of packets. In detail, at each time step, all packets move from their current position, i, to the next node in their path, j, with a probability Qij defined as (3.1)Qij=kjαexp⁡⁡[-β(dit-djt-1)]∑l∈Ωiklαexp⁡⁡[-β(dit-dlt-1)],
where Ωi is the set of neighboring nodes of i, kj is the degree of node j, and dit is the shortest path length between node i and node t. The parameters α and β are tunable parameters with varying range α∈(-∞,∞) and β∈[0,∞). Through numerical simulations, the authors in [29] showed that with appropriate selection of the tunable parameters, the strategy in [29] is superior to the shortest path routing strategy in enhancing the traffic capacity. Furthermore, the authors of [29] pointed out that the strategy in [45, 46] is sensitive to the total number of tasks assigned to the networks. In the case of heavy traffic, the contribution of shortest path length for delivering packets can be ignored, because the diameter of most real communication networks grows only logarithmically with system size [1] and shortest path length is only bound to the diameter value. However, the strategy in [29] is insensitive to the amount of traffic flow in the network. In [39], based on the strategy which considered both shortest path length ingredient and degree ingredient in heterogeneous networks, the authors proposed an improved routing strategy with memory information in scale-free networks. This result was inspired by [47], in which researchers found that when studying local search in power-law communication networks, the search efficiency can be effectively enhanced if retracing the last step is disallowed in random networks. In the strategy with memory information [39], when node A receives a new packet from node B, node A has to record that the new packet is from node B. At the next time step, the packet node A is forbidden to be forwarded back to node B. In this way, the chance that packets are transported back and forth between two distinct nodes is greatly reduced. Figure 2 shows the results of performances in enhancing traffic capacity for both strategies with and without memory information. In Figure 2, α regulates the degree ingredient involved for forwarding packets, and β regulates the shortest path length ingredient involved for forwarding packets. γ denotes the degree exponent of scale-free networks. Results show that traffic capacity can be effectively enhanced by using the strategy with memory information.(a) The traffic capacity rateρc versus the degree exponent γ with β equal to 1. The cases of α=-1, 0, and 1 are marked with asterisks, circles, and squares, respectively. (b) The traffic capacity ρc versus α. The cases of γ=3, 2.5, and 2 are marked with asterisks, circles, and squares, respectively. In both figures, dotted and solid lines are for the routing strategies with and without memory information. Network size is set to 500 in both figures [39].
(a)(b)In [44], the authors proposed a kind of efficient routing strategy. In order to find the optimal routing strategy, the authors define “the efficient path.” For any path between node i and node j as P(i→j):=i≡x0,x1,...,xn-1,xn≡j, define (3.2)L(P(i⟶j):β)=∑i=0n-1k(xi)β,
where k(xi) is the degree of node xi and β is a tunable parameter. The efficient path between i and j is corresponding to the route that makes the sum L(P(i→j):β) minimal. It is obvious that L(β=0) recovers the shortest path routing strategy. It is expected that the system behaves better under the routing rule with β>0 than under the shortest path routing strategy. In [44], the authors concerns how Rc [28], that is, the critical number of generated packets at each time step, varies with β. Here, Rc=Nρc. The simulation results for the critical value Rc as a function of β on BA scale-free networks are illustrated in Figure 3. It can be found that Rc firstly increases with β and then decreases, with the maximal Rc corresponding to β=1. As compared to the shortest path routing strategy (β=0), the traffic capacity is greatly improved, from Rc≈4 when β=0 to Rc≈45 when β=1, more than ten times. However, the authors also found that the average total delivering path length is maximal when β=1. Therefore, they concluded that the system capability in processing information is considerably enhanced at the cost of increasing the average total delivering path length when using the strategy [30].Figure 3
The criticalRc versus β for scale-free networks with size N=1225. Both simulations and theoretical analysis indicate that the maximal value of Rc corresponding to β≈1. The data shown here is the average over 10 independent runs [44].The routing strategies mentioned above, allow each node to have the whole network’s global topological information, which may be practical for small or medium size networks but not for large real communication such as the Internet, WWW [48], peer-to-peer networks [25, 49], or urban transportation system [50, 51]. However, strategies based on local information (each node only knows the information of its neighbors) are favored in large networks due to heavy communication cost on searching global information in networks. Inspired by the study on network search or network navigation on complex networks [47, 52–55], the authors in [56, 57] present a traffic model in which packets are routed only based on local topological information with a single tunable parameter α. The optimized value of α was sought out to maximize the traffic capacity. In this model, each node performs a local search among its neighbors. If the packet’s destination is within the searched area, it is delivered directly to its destination. Otherwise, it is forwarded to a node i, one of the neighbors of the searching node, according to the preferential probability(3.3)Πi=kiα∑jkjα,
where the sum runs over all neighbors of the searing node i, ki is the degree of node i, and α is a tunable parameter. With the delivering capacity of each node set as a constant C, the simulation results show that the optimal performance of the system corresponds to α=-1, which can be observed from Figure 4. Theoretical analyses for the optimal value α=-1 were obtained in [56]. The authors of [56] also pointed out that choosing the optimal α=-1 not only maximizes the traffic capacity but also minimizes the average delivering time. When the delivering capacity of each node is proportional to its degree k, the optimal value of α changes to α=0, as demonstrated in Figure 5. This result indicates that under the conditions of heterogeneous delivering capacity of each node, the random walks strategy is the best choice for routing packets.Figure 4
CriticalRc versus α on a BA scale-free network with network size N=1000 and constant delivery capacity of each node C=10. The maximal of Rc corresponds to α=-1 marked by a dotted line [56].Figure 5
The critical generating rateRc versus α in the case of delivery capacity of each node proportional to its degree Ci=ki. Here, kmin is set to be 3 and network size N=1000. The maximum of Rc corresponds to α=0 marked by a dotted line [56].Actually, the area of information that each router can access can significantly affect the performances of local routing strategy in traffic transport on complex networks. References [58, 59] found that the next-to-nearest routing algorithm can perform much better than the nearest routing algorithm under the random routing strategy. The next-to-near routing algorithm means that a packet can directly be delivered to its destination if the destination is one of the next-to-nearest neighbors of the searching node.The strategy in [56, 57] is only based on local static information, which can only enhance the traffic capacity but cannot considerably reduce the transport time. In [49], the authors proposed a new routing strategy based on local static and dynamical information in scale-free networks. In the routing model of [49], it was assumed that each node has an identical delivering capacity C. A packet is directly delivered to its destination if the destination is one of the direct neighbors of the searing node l. Otherwise, the probability of a neighbor node i to which the packet will be delivered is(3.4)Pl→i=ki(ni+1)β∑jkj(nj+1)β,
where the sum runs over all neighbors of the searching node i, ni is the number of packets in the queue of i and β is a tunable parameter. Also, this model considers the effect of transmission delay on the traffic dynamics. The delay is defined as the number of time steps in receiving updated dynamical information from the neighbors [49]. Figure 6 shows that in the case of no delay, the traffic capacity is considerably reduced when decreasing β until β≈-3. The maximal traffic capacity is only 23 when choosing C=5 under the case of only adopting local topological information [56, 57]. Results show that the traffic capacity is further improved by using the strategy in [49] as compared to the strategy in [56, 57]. The average transport time 〈T〉 is reported in Figure 7. It can be seen that by adopting the strategy in [56, 57], 〈T〉 is approximately independent of R. When R is not too large, 〈T〉 is much shorter by adopting the strategy in [49] than the strategy in [56, 57]. In real communication system, the local dynamical information can be obtained by using the keep-alive messages that router continuously exchange with their peers [45].Figure 6
The network capacityRc versus parameter β for different time delay and for different network size N. The other parameter is C=5 [49].Figure 7
Average transport time〈T〉 versus R for strategies in [49, 56, 57], respectively. α=-1 corresponds to the optimal value of the strategy in [56, 57] and β is the parameter of the strategy in [49]. The network size is set to N=1000 and the node delivering capacity is set to C=5.In [60], the authors proposed another global routing strategy which considers both global topological information and queue length of each node. In this global strategy, the packets are delivered along the path in which the sum of queue length of nodes is a minimum. The path between node i (source) and node j (destination) can be denoted as(3.5)Pij=min⁡⁡∑m=0l[1+n(xm)],
where n(xm) is the queue length of node and l is the path length. Figures 8(a)–8(c) show the evolution of the total packet number Np under the shortest path strategy [29, 43, 44], the efficient strategy proposed in [44], and the global dynamic paths with the network size N=500 and average degree 〈k〉=4. Figure 8(d) compares the relation of order parameter η versus R under the three routing strategies. It can be seen that the traffic capacity under the shortest path strategy [29, 43, 44] is Rc=3. The efficient strategy in [44] has Rc=20 and the global dynamic strategy can reach up to Rc=41. Therefore, the global dynamic strategy can achieve the highest traffic capacity.Evolution in the packet number in the network under different routing strategies [60]. (a) Shortest path routing strategy, (b) Efficient routing strategy in [44], and (c) The global dynamic routing strategy. (d) The order parameter η versus R under the three routing strategies.
(a)(b)(c)(d)Figure9 shows the relation of traffic capacity Rc versus the average degree 〈k〉 and versus the network size N under the three routing strategies [60]. Results show that the traffic capacity under the global dynamic routing strategy is the largest. Because the node queue length changes from time to time, it is computationally time consuming to find the global paths at each time step. Therefore, the authors in [60] introduced a time delay δT for the update of the global queue information and the corresponding paths. They found that with the increment of time delay, the traffic capacity remains almost the same, but the total packet number in system, the traveling time, and the waiting time will increase.(a) The traffic capacityRc versus average degree 〈k〉 with the same network size N=500 under the three routing strategies. (b) The traffic capacity Rc versus the network size N with the same average degree 〈k〉=4 under the three routing strategies [60].
(a)(b)


## 4. “Hard” Strategies

### 4.1. Removing Links

“Hard” strategies mean network topological structure is appropriately changed so that transport efficiency can be improved. Adding or rewiring links are more costly than soft strategies (i.e., designing efficient routing strategies), because adding or rewiring links usually have to consume much financial, manpower or even energy cost. On the contrary, removing links from networks is usually easy to be implemented at low cost. For example, in a high-way network system, some road ways are usually closed at rush hours to alleviate congestion, especially when crowds of people are rushing to offices in the morning or rushing back home in the afternoon. To realize the closure of roadways, traffic administrators need only to block the entries to the roadways, which is easy to be implemented. Another example is the Internet. Network administrators can easily isolate some connections among computers through computer software.In fact, the link removal strategy has been extensively studied to enhance or optimize dynamics of different kinds on complex networks. In [61], the authors pointed out that the removals of nodes or links could alleviate or even mitigate cascades of overloading on networks. In [62], the link-removal strategy was applied in the metabolic network. They pointed out that the removals of metabolic reactions, which represent links in the metabolic network, could improve metabolic performances and rescue defective metabolic networks. In [63], the authors found that the removals of links could also help to enhance synchronization in complex networks of dynamical systems.Literatures on enhancing transport capacity by removing links in communication networks have also been reported. The strategies in [64, 65] were proposed to enhance the traffic capacity by removing certain links among hub nodes in scale-free networks. The strategy proposed in [64], also called high-degree-first (HDF) strategy, first ranks the links according to the value of the product (km×kn), where km and kn are the links’ end-node degrees. Then, links are closed according to this order from large to small. Because hub nodes are usually more important and bear more traffic loads, the links with larger values of (km×kn) are easier to jam. Hence, removing highly congested links can lead to the redistribution of traffic loads along links so as to enhance the overall packet handling and delivering capacity. For convenience, the number of removed links was denoted as Lc. Figure 10 shows the increment of Rc versus Lc under the shortest path routing strategy. Results show that on closing the links according to the order of km×kn, traffic capacity can be remarkably enhanced.Rc versus Lc under the shortest path routing strategy with the network size (a) N=1000 and (b) N=5000. The data are obtained by averaging Rc over ten network realizations [64].
(a)(b)The authors of [64] also investigated the relationship of Rc versus Lc under the local routing strategy [56]. As shown in Figure 11, when Lc increases from 0 to 600, the maximal traffic capacity Rcmax always emerges at α=-1, but its value decreases from 10 to 5. However, when α is far from −1, Lc increases with the number of removed links. In Internet, it has been found that there are fluctuations in information flow [26]. Therefore, the link-removal strategy can be applied to alleviate traffic congestion at times of high flux, and links can be recovered at times of low flux. The essence of the strategy in [65], also called high-betweenness-first (HBF) strategy, is much the same as that of the strategy in [64], but the strategy in [65] ranks the links according to the value of (Bm×Bn), where Bm and Bn are the links’ end-node betweennesses.Figure 11
Rc versus Lc under the local routing strategy with the network size N=1000. The data are obtained by averaging Rc over ten network realizations [64].In [66], the authors pointed out the strategies of [64, 65] to identify the links to be removed in scale-free networks is far from optimal. On the basis of optimizing results which are obtained by using the SA (simulated annealing) algorithm [67, 68], the authors of [66] proposed a link-removal strategy. This new strategy, called variance-of-neighbor-degree-reduction (VNDR) strategy, not only considers the important role of hub nodes, but also balances the amount of packets from each node to its neighbors by reducing the variances of neighbors’ degrees of some nodes. For node i, if the relative variance of neighbors’ degrees (RVND), defined as(4.1)rvar(i)=stdj∈nei(i)⁡(d(j))(1/|nei(i)|)∑j∈nei(i)d(j),
is large (nei(i) is the neighborhood set of node i), then packets are more likely to be routed to hub nodes under the shortest path routing strategy. In (4.1),(4.2)stdj∈nei(i)(d(j))=(d(j)-(1/|nei(i)|)∑j∈nei(i)d(j))2|nei(i)|-1.
Hence, the hubs nodes are more likely to be congested. If the link between the hub node and the node with high RVND is removed, for example, the link between node P and node D is removed in the left figure of Figure 12, the distribution of neighbors’ degree of the node with high RVND will become more even, and therefore, traffic amounts are balanced in the network. Finally, the traffic capacity is enhanced.Illustration of uneven (a) and even (b) distributions of neighbors’ degrees of a central node. NodeP is the central node, and nodes A, B, C, D, and E are five neighbors of node P. ki is the degree of node i.
(a)(b)The VNDR link-removal strategy to enhance traffic capacity in scale-free networks is carried out as follows. For each nodei in the initial network G, the authors in [66] defined(4.3)H(i)=rvar(i)×stdj∈nei(i)(d(j))×d(i).
Choose the node p1 with the maximal value of H. Then, choose the node q1 with the highest degree from the neighborhood set of node p1. Remove the link connecting node p1 and node q1. Then a new network G2 is generated. For the network G2, recompute H for all nodes and choose nodes p2 and q2 in the same way. The whole link-removal process is repeated until a predefined fraction fr of the links is removed. All nodes have to be in one component in the whole process. If the removal of a link causes certain nodes to be disconnected from the original network, the process is no longer executed. Instead, go to deal with the link that connects the node p with the variable H ranked next and the node q with the highest degree in the neighborhood set of node p. The results using SA algorithm are also reported.The performance of the VNDR strategy is evaluated by comparing it with the high-degree-first (HDF) strategy [64] and the high-betweenness-first (HBF) strategy [65]. In conducting the SA searching, the initial and final temperatures are set to 10 and 10-4, respectively. The temperature decreasing coefficient is set to ε%=0.99. For simplicity, the fraction of removed links is denoted as fr. The results of traffic capacity ρc and average shortest path length Lave versus fr under the shortest path routing strategy are shown in Figure 13. It can be found that the VNDR strategy is superior to HDF and HBF link-removal strategies in enhancing the traffic capacity. The superiority of VNDR strategy over HDF and HBF strategies in enhancing traffic capacity under the shortest path routing strategy is rationalized in [66]. Furthermore, the authors in [66] also pointed out that under the shortest path routing strategy, the VNDR strategy can also reduce the average transport time as compared to the HDF and HBF strategies.Illustration ofρc and Lave versus fr under the shortest path routing strategy. Network sizes are set to N=1000 in (a), (b) and N=500 in (c), (d) [66].
(a)(b)(c)(d)


### 4.2. Adding Links

Link-removal strategy is operationally convenient and economical in real communication networks to enhance transport efficiency. However, with the rapid development of society, the sizes of real communication networks are consistently increasing, which brings new challenges to network administrators in charge of network communications. For instance, the numbers of roadways and cities keep on increasing in highway networks, and the number of computers is also increasing explosively in the Internet. But due to the cost incurred in adding new nodes and links to existing networks, real network designers have to be cautious when preparing to add new nodes and links to a given communication network. Otherwise, if new nodes and links are added to an existing network in an improper way, the new links may not be helpful for enhancing transport efficiency while packets are generated on both existing nodes and new nodes, which may aggravate congestion in the network. More links then need to be added into the networks to alleviate congestion with extra cost. Thus, it is necessary to investigate how to add nodes and links in an efficient way so that the traffic capacity can be enhanced maximally.In [69], the authors proposed a strategy that can effectively enhance the traffic capacity via the process of adding nodes and links. They consider two cases. (1). The number of nodes is kept unchanged and only the number of links is allowed to be increased. (2) Both nodes and links are allowed to be added to the existing network. In the strategy of [69], shortcut links are added among nodes that have the longest shortest path lengths. The shortcut links are placed in proper positions to avoid packets flowing through hub nodes so that there are not too many packets accumulated on hub nodes.In a scale-free network withN nodes and L links, for simplicity, the authors of [69] denote the fraction of new added links over the total L existing links as fa. Figure 14 shows the traffic capacity Rc and the average shortest path length lave versus fa under the shortest path routing strategy. From Figure 14(a), it is found that both the strategy of [69] and the random strategy can enhance the traffic capacity Rc when links are added into networks. But the traffic capacity Rc is enhanced more using the strategy of [69] than using the random strategy.The traffic capacityRc and the average shortest path length lave as a function of fa under the shortest path routing strategy. In each figure, the gray and black colors are for the cases with m0=m=3 andm0=m=5, respectively. The network size is set to N=500. The circles, asterisks, and plus signs are the results of the strategy in [69], the random strategy, and the strategy that adds links among hub nodes, respectively. Each result is obtained by averaging over fifty different network configurations and ten independent link-adding processes for each network realization when executing our strategy and the random strategy.
(a)(b)For the case that both nodes and links are allowed to be added into networks under the shortest path routing strategy, the authors of [69] compared their strategy with the “degree preferential attachment” mechanism and the low-degree-first strategy. The results are shown in Figure 15. Results show that in the process of adding nodes and links to existing networks under the shortest path routing strategy, the strategy in [69] can effectively enhance the traffic capacity of networks at the cost of lengthening the average shortest path lengths.[69] The traffic capacity Rc and the average shortest path length lave as a function of the network size N under the shortest path routing strategy. Figures 15(a) and 15(b) start from scale-free networks with N=500 nodes, while Figures 15(c) and 15(d) start from scale-free networks with N=1000 nodes. Each result is obtained by averaging over fifty different network configurations. In each figure, the cases of m0=m=3 and m0=m=5 are marked with gray and black colors. Dotted, dashed, and solid lines are for the “degree preferential attachment” mechanism, the low-degree-first strategy, and our proposed strategy, respectively.
(a)(b)(c)(d)It is worth noting that there is an underlying relation between cascading dynamic [70–73] and congestion of packet traffic [74]. Cascading dynamics means that breakdown on a global scale can be triggered by small failures on nodes through the mechanism of cascading. Typical examples include large-scale blackouts of power grids and heavy congestion on the Internet and so forth. In [74], the authors pointed out that the smaller B̅m is, the more robust a network is against cascades. On the other hand, the traffic capacity, Rc, can be estimated as [26](4.4)Rc=N(N-1)B̅m.
This means that the maximal node betweenness can determine both the robustness against cascades and the traffic capacity of a network. Removing or adding links has been proved to be able to effectively enhance the traffic capacity, which means that B̅m can be effectively reduced. Therefore, the robustness against cascades of a network can also be effectively enhanced by using appropriate link-removal or link-adding strategies.The key purpose of studying routing is to study performances of networks such as delay, admission control, and resource allocation [14, 15]. That is particularly true in real-time systems. Thus, this survey is only a conventional part of contents from a view of computer science. The recent contents are associated with network calculus. Moreover, the performances of networks for traffic transport are highly related to the scales observed. Interested reader can refer to [14–18] for their further studies.


## 4.1. Removing Links

“Hard” strategies mean network topological structure is appropriately changed so that transport efficiency can be improved. Adding or rewiring links are more costly than soft strategies (i.e., designing efficient routing strategies), because adding or rewiring links usually have to consume much financial, manpower or even energy cost. On the contrary, removing links from networks is usually easy to be implemented at low cost. For example, in a high-way network system, some road ways are usually closed at rush hours to alleviate congestion, especially when crowds of people are rushing to offices in the morning or rushing back home in the afternoon. To realize the closure of roadways, traffic administrators need only to block the entries to the roadways, which is easy to be implemented. Another example is the Internet. Network administrators can easily isolate some connections among computers through computer software.In fact, the link removal strategy has been extensively studied to enhance or optimize dynamics of different kinds on complex networks. In [61], the authors pointed out that the removals of nodes or links could alleviate or even mitigate cascades of overloading on networks. In [62], the link-removal strategy was applied in the metabolic network. They pointed out that the removals of metabolic reactions, which represent links in the metabolic network, could improve metabolic performances and rescue defective metabolic networks. In [63], the authors found that the removals of links could also help to enhance synchronization in complex networks of dynamical systems.Literatures on enhancing transport capacity by removing links in communication networks have also been reported. The strategies in [64, 65] were proposed to enhance the traffic capacity by removing certain links among hub nodes in scale-free networks. The strategy proposed in [64], also called high-degree-first (HDF) strategy, first ranks the links according to the value of the product (km×kn), where km and kn are the links’ end-node degrees. Then, links are closed according to this order from large to small. Because hub nodes are usually more important and bear more traffic loads, the links with larger values of (km×kn) are easier to jam. Hence, removing highly congested links can lead to the redistribution of traffic loads along links so as to enhance the overall packet handling and delivering capacity. For convenience, the number of removed links was denoted as Lc. Figure 10 shows the increment of Rc versus Lc under the shortest path routing strategy. Results show that on closing the links according to the order of km×kn, traffic capacity can be remarkably enhanced.Rc versus Lc under the shortest path routing strategy with the network size (a) N=1000 and (b) N=5000. The data are obtained by averaging Rc over ten network realizations [64].
(a)(b)The authors of [64] also investigated the relationship of Rc versus Lc under the local routing strategy [56]. As shown in Figure 11, when Lc increases from 0 to 600, the maximal traffic capacity Rcmax always emerges at α=-1, but its value decreases from 10 to 5. However, when α is far from −1, Lc increases with the number of removed links. In Internet, it has been found that there are fluctuations in information flow [26]. Therefore, the link-removal strategy can be applied to alleviate traffic congestion at times of high flux, and links can be recovered at times of low flux. The essence of the strategy in [65], also called high-betweenness-first (HBF) strategy, is much the same as that of the strategy in [64], but the strategy in [65] ranks the links according to the value of (Bm×Bn), where Bm and Bn are the links’ end-node betweennesses.Figure 11
Rc versus Lc under the local routing strategy with the network size N=1000. The data are obtained by averaging Rc over ten network realizations [64].In [66], the authors pointed out the strategies of [64, 65] to identify the links to be removed in scale-free networks is far from optimal. On the basis of optimizing results which are obtained by using the SA (simulated annealing) algorithm [67, 68], the authors of [66] proposed a link-removal strategy. This new strategy, called variance-of-neighbor-degree-reduction (VNDR) strategy, not only considers the important role of hub nodes, but also balances the amount of packets from each node to its neighbors by reducing the variances of neighbors’ degrees of some nodes. For node i, if the relative variance of neighbors’ degrees (RVND), defined as(4.1)rvar(i)=stdj∈nei(i)⁡(d(j))(1/|nei(i)|)∑j∈nei(i)d(j),
is large (nei(i) is the neighborhood set of node i), then packets are more likely to be routed to hub nodes under the shortest path routing strategy. In (4.1),(4.2)stdj∈nei(i)(d(j))=(d(j)-(1/|nei(i)|)∑j∈nei(i)d(j))2|nei(i)|-1.
Hence, the hubs nodes are more likely to be congested. If the link between the hub node and the node with high RVND is removed, for example, the link between node P and node D is removed in the left figure of Figure 12, the distribution of neighbors’ degree of the node with high RVND will become more even, and therefore, traffic amounts are balanced in the network. Finally, the traffic capacity is enhanced.Illustration of uneven (a) and even (b) distributions of neighbors’ degrees of a central node. NodeP is the central node, and nodes A, B, C, D, and E are five neighbors of node P. ki is the degree of node i.
(a)(b)The VNDR link-removal strategy to enhance traffic capacity in scale-free networks is carried out as follows. For each nodei in the initial network G, the authors in [66] defined(4.3)H(i)=rvar(i)×stdj∈nei(i)(d(j))×d(i).
Choose the node p1 with the maximal value of H. Then, choose the node q1 with the highest degree from the neighborhood set of node p1. Remove the link connecting node p1 and node q1. Then a new network G2 is generated. For the network G2, recompute H for all nodes and choose nodes p2 and q2 in the same way. The whole link-removal process is repeated until a predefined fraction fr of the links is removed. All nodes have to be in one component in the whole process. If the removal of a link causes certain nodes to be disconnected from the original network, the process is no longer executed. Instead, go to deal with the link that connects the node p with the variable H ranked next and the node q with the highest degree in the neighborhood set of node p. The results using SA algorithm are also reported.The performance of the VNDR strategy is evaluated by comparing it with the high-degree-first (HDF) strategy [64] and the high-betweenness-first (HBF) strategy [65]. In conducting the SA searching, the initial and final temperatures are set to 10 and 10-4, respectively. The temperature decreasing coefficient is set to ε%=0.99. For simplicity, the fraction of removed links is denoted as fr. The results of traffic capacity ρc and average shortest path length Lave versus fr under the shortest path routing strategy are shown in Figure 13. It can be found that the VNDR strategy is superior to HDF and HBF link-removal strategies in enhancing the traffic capacity. The superiority of VNDR strategy over HDF and HBF strategies in enhancing traffic capacity under the shortest path routing strategy is rationalized in [66]. Furthermore, the authors in [66] also pointed out that under the shortest path routing strategy, the VNDR strategy can also reduce the average transport time as compared to the HDF and HBF strategies.Illustration ofρc and Lave versus fr under the shortest path routing strategy. Network sizes are set to N=1000 in (a), (b) and N=500 in (c), (d) [66].
(a)(b)(c)(d)


## 4.2. Adding Links

Link-removal strategy is operationally convenient and economical in real communication networks to enhance transport efficiency. However, with the rapid development of society, the sizes of real communication networks are consistently increasing, which brings new challenges to network administrators in charge of network communications. For instance, the numbers of roadways and cities keep on increasing in highway networks, and the number of computers is also increasing explosively in the Internet. But due to the cost incurred in adding new nodes and links to existing networks, real network designers have to be cautious when preparing to add new nodes and links to a given communication network. Otherwise, if new nodes and links are added to an existing network in an improper way, the new links may not be helpful for enhancing transport efficiency while packets are generated on both existing nodes and new nodes, which may aggravate congestion in the network. More links then need to be added into the networks to alleviate congestion with extra cost. Thus, it is necessary to investigate how to add nodes and links in an efficient way so that the traffic capacity can be enhanced maximally.In [69], the authors proposed a strategy that can effectively enhance the traffic capacity via the process of adding nodes and links. They consider two cases. (1). The number of nodes is kept unchanged and only the number of links is allowed to be increased. (2) Both nodes and links are allowed to be added to the existing network. In the strategy of [69], shortcut links are added among nodes that have the longest shortest path lengths. The shortcut links are placed in proper positions to avoid packets flowing through hub nodes so that there are not too many packets accumulated on hub nodes.In a scale-free network withN nodes and L links, for simplicity, the authors of [69] denote the fraction of new added links over the total L existing links as fa. Figure 14 shows the traffic capacity Rc and the average shortest path length lave versus fa under the shortest path routing strategy. From Figure 14(a), it is found that both the strategy of [69] and the random strategy can enhance the traffic capacity Rc when links are added into networks. But the traffic capacity Rc is enhanced more using the strategy of [69] than using the random strategy.The traffic capacityRc and the average shortest path length lave as a function of fa under the shortest path routing strategy. In each figure, the gray and black colors are for the cases with m0=m=3 andm0=m=5, respectively. The network size is set to N=500. The circles, asterisks, and plus signs are the results of the strategy in [69], the random strategy, and the strategy that adds links among hub nodes, respectively. Each result is obtained by averaging over fifty different network configurations and ten independent link-adding processes for each network realization when executing our strategy and the random strategy.
(a)(b)For the case that both nodes and links are allowed to be added into networks under the shortest path routing strategy, the authors of [69] compared their strategy with the “degree preferential attachment” mechanism and the low-degree-first strategy. The results are shown in Figure 15. Results show that in the process of adding nodes and links to existing networks under the shortest path routing strategy, the strategy in [69] can effectively enhance the traffic capacity of networks at the cost of lengthening the average shortest path lengths.[69] The traffic capacity Rc and the average shortest path length lave as a function of the network size N under the shortest path routing strategy. Figures 15(a) and 15(b) start from scale-free networks with N=500 nodes, while Figures 15(c) and 15(d) start from scale-free networks with N=1000 nodes. Each result is obtained by averaging over fifty different network configurations. In each figure, the cases of m0=m=3 and m0=m=5 are marked with gray and black colors. Dotted, dashed, and solid lines are for the “degree preferential attachment” mechanism, the low-degree-first strategy, and our proposed strategy, respectively.
(a)(b)(c)(d)It is worth noting that there is an underlying relation between cascading dynamic [70–73] and congestion of packet traffic [74]. Cascading dynamics means that breakdown on a global scale can be triggered by small failures on nodes through the mechanism of cascading. Typical examples include large-scale blackouts of power grids and heavy congestion on the Internet and so forth. In [74], the authors pointed out that the smaller B̅m is, the more robust a network is against cascades. On the other hand, the traffic capacity, Rc, can be estimated as [26](4.4)Rc=N(N-1)B̅m.
This means that the maximal node betweenness can determine both the robustness against cascades and the traffic capacity of a network. Removing or adding links has been proved to be able to effectively enhance the traffic capacity, which means that B̅m can be effectively reduced. Therefore, the robustness against cascades of a network can also be effectively enhanced by using appropriate link-removal or link-adding strategies.The key purpose of studying routing is to study performances of networks such as delay, admission control, and resource allocation [14, 15]. That is particularly true in real-time systems. Thus, this survey is only a conventional part of contents from a view of computer science. The recent contents are associated with network calculus. Moreover, the performances of networks for traffic transport are highly related to the scales observed. Interested reader can refer to [14–18] for their further studies.


## 5. Concluding Remarks

The heavy traffic loads in real networked communication systems motivate the intense study of traffic dynamics on complex networks in recent years. The main goal is to enhance transport efficiency so that traffic congestions on complex networks can be alleviated. Generally speaking, the strategies which can enhance the traffic capacity can be categorized into two classes: designing efficient routing strategies and making appropriate adjustments to network structures. Many strategies have been proved to be able to enhance the transport efficiency and are helpful for people in understanding and controlling traffic congestion in real networks.Although the issues of enhancing transport efficiency have been extensively reported in the literatures, there are still many open questions to be studied. Real communication networks are usually much more complicated than the traffic routing model. Other dynamics such as the virus prevalence and cascading breakdown, may also be mixed with the traffic routing dynamics. A few open questions to be solved in future work are listed as follows.(1)
The cascading breakdown dynamics can be incorporated with the traffic routing dynamics. A node or a link may lose its function in delivering packets due to traffic congestion on this node or link. Therefore, the node or the link will be removed from the network. As a result, the traffic capacity may be reduced. Under this circumstance, it is thus interesting to study the relationship between the two kinds of dynamics.(2)
It is not always the case in real communication networks that each node in the network can generate packets. Some nodes (i.e., generators) may only generate and send packets to other nodes but do not receive packets from elsewhere. The rest of nodes (i.e., receivers) only receive packets from elsewhere but do not generate and send packets to other nodes. The positions of generators may have impacts on the transport efficiency of packets. It is neccesary, therefore, to study how to place generators and receivers in networks so that the transport efficiency can be maximized.(3)
Most current studies about traffic routing dynamics on complex networks is based on traffic routing models. However, due to complexity of real communication networks, traffic routing models cannot fully reflect the characteristics of real communication networks. More attention should be focused on revealing new characteristics of real communication networks rather than only study traffic routing models.



---

*Source: 732698-2011-09-20.xml*