Since Welsh and Barabàsi^[1] proposed networks with minimal world properties and scale-free features, the structure and dynamics of complex networks have attracted a tremendous amount of interest and attention from the physics community. In past decades, complex networks have become the focus of research in different fields,^[2–7] such as mechanics, physics, biology, control systems, communication technology, society, economic and military, etc. The complex network consists of a large number of nodes and the perplexing relationships between the nodes, which widely exists in the nature, biology and Engineering fields.^[8] Research on the network topological structure is based on the research methods of statistical physics, while these methods can also be applied to the study on the dynamic characteristics of complex networks, such as network congestion, network search etc.^[9]

As is known to all, the booming of loads has challenged the efficiency and reliability for all kinds of network. How to guarantee the quality of service of each load with finite resources without negotiating the performance of the network is a problem that urgently needs to be coped with. Designing or optimizing the routing strategy is a perfect way to solve the problem. Without changing the topology and large cost,^[10] the network could perform better when equipped with a new and suitable strategy. In this light, to find optimal strategies for traffic routing is one of the important issues we have to address. There have been many previous studies to understand and control traffic congestion on networks, with a basic assumption that the network has a homogeneous structure.^[11–24]

The most classical strategy among traditional routing strategies is the Shortest Path Routing Strategy (SR). Packets will choose paths with the smallest hops, which means they will reach the destination at the fastest speed. Sadly, congestion quite easily shows up at some key nodes.^[11,12] Yan et al.^[13] proposed a strategy called the Efficient Routing Strategy (ER). One path will be chosen only if the sum of the degree of nodes it covers is the smallest. This strategy releases the state of traffic congestion largely. Pu et al.^[14] put forward an Active Routing Strategy, which is an optimized strategy of ER. Packets are less sensitive to nodes with relatively large degrees, these nodes are not impossible or hardly chosen, and the capacity of all kinds of nodes will be utilized more thoroughly. A Probability Routing Strategy is brought forward in Ref. [15]. This strategy makes a balance between SR and ER to make the most of hub nodes.

Danila et al.^[16,17] adopted the idea of extremum optimizing. By avoiding nodes with the largest betweenness centrality, partial loads are distracted to the margin of the network. Chen et al.^[18] put forward a unified algorithm about betweenness centrality, and an optimized protocol (OP) is designed. Tang et al.^[19] discarded a First In First Out (FIFO) strategy and performed better by enabling packets to choose the next hop based on the condition of the potential next node. Tang^[20] proposed a self-adaptive routing strategy by analyzing the state of the network to cope with time-variant loads. LING et al.^[21] put out a method to allocate loads based on nodes’ capacities. This paper^[22] takes throughout and complexity into consideration and puts forward a pheromone-based routing strategy. A local routing strategy on complex networks is proposed in Ref. [23], which is used to evaluate the importance of nodes, and the probability of forwarding packets to a neighbor node is adaptively adjusted by the importance of the node and the state of the network. A new optimization algorithm was proposed to improve the network performance in Ref. [24].

However, the present routing strategies consider that all loads are homogeneous and are treated as unified. Actually, different loads enquire different qualities of service. In the real traffic network, vehicles, like fire trucks, ambulances, and police cars, need paths with the shortest time, even if traffic congestion exists. In the Internet, real-time voice service packets are delay-sensitive. A slight fluctuation of the network state could cause choppy voice, even drop the call. Express deliveries like urgent dispatch and seafood in logistics networks require high real-time performance. From the view of real-time, fire trucks in the traffic network and real-time voice service should be guaranteed with the shortest transmission delay, shortest length of path, and highest priorities. Otherwise, transmission delay on fire trucks and urgent dispatch will cause irreparable damage, meanwhile other vehicles and delivery will suffer more transmission jam. Our motivation comes from the desire to understand the influence of flow difference on the traffic dynamics on a network, as existing works in this direction often assume homogeneity for the underlying network. In this paper, we treat delay-sensitive loads as privileged-packets. On the contrary, the rest of the loads are called common packets. When packets of different priorities show up in the network, the present routing strategy will not work anymore. According to this situation, in this paper we put forward an optimized routing strategy called the Privileged Routing Strategy (PR) and design a routing strategy RS-MP with multiple priorities by which packets are classified into privileged-packets and common-packets on complex networks due to the difference of traffic flow conditions. To fully characterize the node busy degree we introduce a new factor BJ–Joint Betweenness Centrality. By optimizing BJ, we can achieve the desired effect that RS-MP can guarantee privileged-packets with the shortest path length and smallest delay, and maximized throughout capacity for common packets in the no-congestion state.

To make our routing strategy more clear, we need to specify some parameters of the network. For the complex network we considered, all the nodes are able to receive, transmit, and forward packets, in other words, they can all act as hosts and routers. The length of buffer queue is set to be infinite. The processing capacity of nodes is shown as C_i, which means the max number of packets processed by node i. In this paper, we assume all the nodes share the same process capacity, C_i = 1. At each time slot, R number of flow packets are generated. Among these packets, privileged-packets’ number is R_P and only take up a tiny small amount. While the rest ones are common packets, whose number is R_C. The starting and ending point of each new generated packet are randomly picked, and they move automatically to the routing strategy until they are wiped out of the network.

As R keeps increasing and exceeds one certain value R_C, the number of newly generated packets goes over the transmission capacity of the network. At this time, packets become piping up at some certain nodes, which means the appearance of traffic congestion and the state of the network has turned from a free stream state to a congestion state.^[13] To sum up, R_C represents the max number of packets that can be transmitted by the network in one time slot, and is a key parameter to the overall performance of the network.

The larger the betweenness centrality of some nodes, the higher the probability they will face traffic congestion.^{[12,21,22,24]} The betweenness centrality of nodes B_k represents the proportion of paths that cover these nodes over the whole paths in the network.^[22] As equation (1) shows, σ(i, j) is the number of paths from source to destination, and the σ(i, k, j) is the number of paths that contain node K.

Only when equation (2) is satisfied, can the network that contains N nodes not face traffic congestion. Suppose the largest betweenness centralities among all the nodes is B_max, the critical value R_C is shown in Eq. (3). So the goal of maximizing R_C can be converted to minimizing B_max.

In the network, different loads focus on different parameters. Privileged-packets need the assurance of real-time quality, while common packets rely more on overall throughout capacity. The main idea of this paper is to firstly guarantee the real-time quality of privileged-packets while promoting the throughout capacity of common packets as large as possible.

3.3. Simulation results

We build a simulation model with the BA network, the total number of nodes N = 200, the initial value is set to m₀ = 3, with the increase of nodes, each time increase 3 edges. In the simulation, each time step generates an R packet, where the maximum number of privileged packets is R_P, and the common packet is R_C. For each R, the simulation runs 1000 steps, the final result takes the average of the last 200 steps. Next, we will carry out the simulation experiment in the distribution of BJ, the network throughput, the average delay, and so on, the routing strategy of this paper (PR) and ER, DAN, SR, and OP are compared.

3.3.1. Distribution of BJ

The different routing tables are respectively corresponding to the privileged-packets and the common-packets, respectively, the number of betweenness centrality is B_P, B_C, and BJ, respectively, the maximum value is B_Pmax, B_Cmax, and BJ_max. The larger the value of betweenness centrality, the higher the likelihood they will face traffic congestion. In the case of privileged load, the BJ_max node is the most prone to congest, but not the corresponding node of B_Pmax and B_Cmax. From Table 1 it can be seen that the ID of the B_Pmax, B_Cmax, and BJ_max nodes are not the same. When SR, ER, DAN, and OP four kinds of algorithms are optimized by PR, the value of BJ_max is reduced. Among them, the SR algorithm decreases the maximum, decreases from 13470 to 1608, the decrease rate is 88%, ER, DAN, and OP algorithms are optimized 34%, 37%, and 34% respectively. The PR optimization algorithm has better optimization results, and the main reason is that the PR algorithm makes the path as far as possible to avoid nodes of a large number of BJ, and the node of the network traffic flow to the light load transfer, thereby reducing the value of BJ_max.

Table 1.

Table 1.

Table 1. The variation of BP, BC, and BJmax for four different routing strategies in the case of before and after PR optimization, where network size N = 200, RP = 2. . BPmax/node ID BCmax/node ID BJmax/node ID SR 8033/1 8033/1 13470/1 PR 7011/1 1578/100 1608/1 ↓80% ↓88% ER 8033/1 2155/48 2294/48 PR 7235/1 1504/182 1522/4 ↓30% ↓34% DAN 8033/1 1993/19 2465/4 PR 7623/1 1532/130 1555/4 ↓23% ↓37% OP 8033/1 1408/46 2360/1 PR 6805/1 1531/148 1552/3 ↑9% ↓34%

Table 1. The variation of BP, BC, and BJmax for four different routing strategies in the case of before and after PR optimization, where network size N = 200, RP = 2. .

As shown in Fig. 1, the distribution of nodes’ BJ is more uniform after the PR optimization, which indicates that the processing capability of the nodes is more fully utilized. In the case of the priority of the privilege packet in real time, it is still effective to ensure the normal packet without congestion transfer capability.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. Distribution of BJ for four different routing strategies in the case of before and after PR optimization, where network size N = 200, RP= 2. (a) Distribution of BJ for SR, (b) distribution of BJ for ER, (c) distribution of BJ for DAN, and (d) distribution of BJ OP.

As shown in Eq. (8), the BJ_max determines the quality of the common-packet’ routing strategy, the smaller the value of BJ_max, the smaller the possibility of traffic congestion would be. Existing routing strategies, such as SR, DAN, ER, and OP, have not considered the existence of privileged loads, so actually the BJ_max is B_max.

3.3.2. Network throughput

The method of analyzing the network free flow to the congestion flow is shown in the Eq. (10). Among them, the H represents an order parameter, and ΔW = W(t + Δt) − W(t), W(t) represents the total load of the network at the time of t, and ⟨⋯⟩ represents the average value of the time window Δt. When the number of new flow packets in the unit time exceeds the critical value R_C, the traffic congestion occurs in the network, and the congestion of the whole network will continue to increase with the increasing of flow packets, so the maximum throughput of R_C is usually used to characterize the network.

As can be seen from Fig. 2, the number of successful packets is less than that of the new flow packets with the R increasing to a critical value R_P. As R increases to a critical value R_P, the network enters the congestion state. Before optimization, the critical R_C of SR algorithms is the first to have the phrase change, the effect of OP is the best with the maximum of R_C, and the critical R_C of ER is 13, and the critical R_C of DAN is about 14. After optimization, the SR, DAN, ER, and OP four routing strategies get better performance, and the critical R_C has been improved, in which the SR gets the largest improvement R_C from 3 to 14, the increase of 367%, ER 15%, DAN 14%, and OP 13%. In view of comprehensive Fig. 2, the PR optimization algorithm is proposed in this paper to achieve a cooperative optimization between privileged-packets and common-packets.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. H versus R for four different routing strategies in the case of before and after PR optimization, where N = 200, RP = 2. (a) H versus R for SR, (b) H versus R for ER, (c) H versus R for DAN, and (d) H versus R for OP.

3.3.3. The impact of the number of privileged packets

The number of privileged loads in the network is small, but the change of the number (R_P) will still have an impact on the network performance. Take the ER routing strategy as an example, figure 3 and Table 2 show the impact of the change in the number of privileged packets. With the increase of R_P, the function of PR optimization algorithm is more and more obvious. The bigger the value of the R_P, the better the effect would be made. When the value of R_P is 4, the privilege packets in the network have begun to cause congestion. In this paper, we assume that the privileged-packets have high importance and cannot be congested. So we do not have to consider it when the value of R_P is greater than 5.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. The variation of R for ER in the case of before and after PR optimization with different RP, where N = 200. (a) The variation of R when RP = 0, (b) the variation of R when RP = 1, (c) the variation of R when RP = 2, (d) the variation of R when RP = 3, and (e) the variation of R when RP = 4.

Table 2.

Table 2.

Table 2. The variation of BJmax by using the efficient routing (ER) in the case of before and after PR optimization with different RP, where N = 200. . RP = 0 RP = 1 RP = 2 RP = 3 RP = 4 ER 2155/48 2223/48 2294/48 2371/48 3441/1 PR 1353/61 1483/1 1522/4 1575/1 1663/1 ↓37% ↓33% ↓34% ↓34% ↓52%

Table 2. The variation of BJmax by using the efficient routing (ER) in the case of before and after PR optimization with different RP, where N = 200. .

3.3.4. Average path length

The average path length represents the total hop number of packets traversed in the process of flow transmission, and it is an important parameter that measures the routing efficiency. From Table 3 it can be seen that the average path length of the privileged packet is not changed when SR, ER, DAN, and OP algorithms are optimized by PR, while the average packet is significantly increased. Among them, the change of the SR algorithm is the biggest, the rate of the increase is 43%. ER, DAN, and OP algorithms were increased by 14%, 15%, and 10% respectively. This shows that the PR optimization algorithm proposed in this paper makes the path as far as possible to avoid larger joint betweenness centrality node, a longer strategy is used to avoid more prone to congestion nodes, sacrificed by the average path length for network throughput.

Table 3.

Table 3.

Table 3. The average path length for four different routing strategies in the case of before and after the PR optimization, where N = 200, RP = 2. . LP LC SR 3.8768 3.8768 PR 3.8768 5.5575 ↑43% ER 3.8768 4.8803 PR 3.8768 5.564 ↑14% DAN 3.8768 4.6306 PR 3.8768 5.3339 ↑15% OP 3.8768 4.9808 PR 3.8768 5.4964 ↑10%

Table 3. The average path length for four different routing strategies in the case of before and after the PR optimization, where N = 200, RP = 2. .

This paper addresses the influence of different traffic flows and designs a routing strategy RS-MP with multiple priorities on complex networks. In this paper, flow packets are divided into privileged-packets and common-packets. The privileged-packets route by the shortest path routing strategy and do not need to queue up. For the common-packets, a new combined optimization strategy (PR) is designed by introducing a new factor BJ_max, which makes the BJ_max minimum. The simulation results show that the factor BJ_max can represent the importance of the network nodes in the routing process. What is more, we can conclude from the simulation results that the privileged-packets are always in the shortest path and still capable of keeping the delay minimal, even when the network is in a congested state. For the common-packets, the PR algorithm has the optimal effect on the existing routing strategies, and the optimized networks’ non-blocking transmit capacity has been greatly improved. Overall, the joint optimization strategy (PR) with priority has the universal property. PR maxmized the network’s non-congestion transmission ability while ensuring the priority of the privileged-packets.