Figures
Abstract
Packets transmitting in real communication networks such as the Internet can be classified as time-sensitive or time-insensitive. To better support the real-time and time-insensitive applications, we propose a two-level flow traffic model in which packets are labeled as level-1 or level-2, and those with level-1 have higher priority to be transmitted. In order to enhance the traffic capacity of the two-level flow traffic model, we expand the global dynamic routing strategy and propose a new dynamic source routing which supports no routing-flaps, high traffic capacity, and diverse traffic flows. As shown in this paper, the proposed dynamic source routing can significantly enhance the traffic capacity and quality of time-sensitive applications compared with the global shortest path routing strategy.
Citation: Jiang Z-Y, Liang M-G, Wu J-J (2013) Dynamic Source Routing Strategy for Two-Level Flows on Scale-Free Networks. PLoS ONE 8(12): e82162. https://doi.org/10.1371/journal.pone.0082162
Editor: Timothy Ravasi, King Abdullah University of Science and Technology, Saudi Arabia
Received: April 27, 2013; Accepted: October 21, 2013; Published: December 12, 2013
Copyright: © 2013 Jiang et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Funding: This work is supported by the Ministry of Science and Technology of China under Grant No. 2007AA01Z203. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
Competing interests: The authors have declared that no competing interests exist.
Introduction
In the past two decades, a variety of real-world networks are demonstrated to have small-world phenomenon [1] and scale-free properties [2], [3], such as the Internet, World Wide Web (WWW), highway networks, social networks, etc. The dynamic traffic processes of network have attracted much research interest. In order to improve the traffic capacity of the complex communication networks, a lot of research has been done in three aspect: designing efficient routing strategy [4]–[25], optimizing network strucure [26]–[31] and reallocating the finite network resources [32]–[40] such as node’s delivering capacity, link’s bandwidth, and queue resources. Compared with the high implementation cost of changing network structure and reallocating finite network resources, developing a better routing strategy is preferable to improve the network traffic capacity.
In the global dynamic routing strategy [22], the path between any source node and destination node
is defined as the path with minimum sum of queue length of nodes, which is denoted as
(1)where
is the queue length of node
and
is the path length. Because global dynamic routing strategy considers the real-time queue length of nodes as routing costs to dramatically redistribute the overall traffic on all nodes, the traffic capacity of network achieves the highest value among recently proposed routing strategies so far [22].
However, the global dynamic routing enhances traffic capacity of network at the cost of longer packet traveling time from source to destination, and might cause routing flaps in real communication networks. Further more, several kinds of applications in the Internet such as video conferences, telephone communication are quite time-sensitive, while some other such as email services are relatively time-insensitive which can tolerate longer packet traveling time. Therefore, in this paper, we introduce two different kinds of traffic flow in the traffic model which is not considered in previous studies. To guarantee the efficiency of time-sensitive applications, we divide all flows in the network into two levels: the first is time-sensitive and the other one is time-insensitive. In order to optimize the packet transportation process in this two-level flow traffic model, we propose one dynamic source routing(DS), in which each data packet carries the complete path information from its source to destination. The explicit path of each packet is computed once the packet is generated. Intermediate nodes need not to keep routing table, and no routing flaps occur any more under this expanded global dynamic routing strategy.
This paper is organized as follows. In the following section, the network model, two-level flow traffic model, and the dynamic source routing strategy for two-level flows are described in detail. Then the simulation results are presented and discussed. The paper is concluded in the last section.
The Models and the Routing Strategy
Empirical studies indicate that many real complex network structures such as the Internet and the WWW are heterogeneous with a power-law degree distribution , and many networks models have been raised. Among them, the Barabási-Albert (BA) network model with
is well-known and widely used. Without loss of generality, we adopt the BA network model in this paper. The construction of a BA network is as follows. Starting from
fully connected nodes, at each step, a new node with
(
) edges are added to the existing network, and the other end of each new edge is chosen preferentially according to the probability
(2)where
is the degree of node
, and
runs over all existing nodes in the network. The growth process of BA scale-free network is terminated once the number of total nodes in the network reaches the scale we need.
Network model is the infrastructure on which the traffic dynamics take place. Traffic model reveals the dynamic running progress of traffic on the network model. To better support distinguishing traffic flows on BA model like networks, here we present one two-level flow traffic model which is described as follows. Each node is considered as both host and router to generate packets or forward packets. Each node can deliver at most (here, we set
) packets at each time step to its immediate neighbors and maintains two queues, one for level-1 packets and the other one for level-2 packets. At each time step,
packets are generated in the network with randomly chosen sources and destinations. A fraction of these
packets are labeled with level-1 as the time-sensitive packets, the others are time-insensitive ones with level-2. Level-1 packets are forwarded with higher priority than the level-2 ones. Only when the level-1 queue is empty, packets in level-2 queue then can be sent. The path between source node
and destination
is denoted as
(3)where
and
are the queue length of level-1 and level-2 on node
respectively, and
for level-1 and
for level-2 when computing path. The first-in-first-out (FIFO) discipline is applied for each queue. Once one packet arrives at its destination, it is removed from the system. If there are more than one paths between two nodes with equal minimum cost, we randomly choose one.
The network traffic capacity can be measured by the maximal packet generation rate , at which the phase transition switches from free flow state to congested flow state. It can be denoted by the order parameter [41]
(4)where
,
indicates the average time windows of width
, and
is the total packets’ number within the network at time
. When
, new generated packets and the removed packets are balanced, and no congestion occurs. With increasing packet generation rate
,
, the inflow exceeds the outflow and some nodes in the network begin to be jammed.
Simulation Results
For this two-level flow traffic model, we denote the fraction of level-1 packets as , then portion
for level-2 packets. Level-1 packets are sent prior to level-2 packets. To do the comparisons, in this paper, we also apply the global shortest path routing strategy for the two-level flow traffic model. Firstly, we investigate the evolution of traffic capacity
with different
under the shortest path routing and dynamic source routing strategy. In our simulations, for each packet generation rate
, we do 10000 time steps to calculate the order parameter
for two-level flow traffic model.
As shown in Figure 1, when or
, all packets are with the same level, and the traffic capacity
achieves the highest value
in our simulations. When
,
decreases with
; while when
, the traffic capacity increases with
. Under the global shortest path routing,
for all
. In many real complex networks, such as the Internet, in order to guarantee the quality of transmission of level-1 packets,
is more realistic and reasonable. Our results show that dynamic source routing can effectively enhance the traffic capacity compared with the shortest path routing.
Network parameters: , average degree
. Curves with solid circles and solid squares represent traffic capacity
under DS and SP respectively.
As discussed in Ref. [9], the path one packet traverses through with the shortest length is not necessarily the quickest way, when considering the presence of possible traffic congestion and waiting time along the shortest paths. Queues of central nodes that one packet easily chooses to pass through to arrive at its destination are longer than other non-center nodes, and the waiting time for one packet on central nodes is much longer. Packets are delayed and thus the whole network get congested. Dynamic source routing strategy computes the path for each packet based on the current traffic load on each node. It can bypass the central nodes and shorten the waiting time of the packets.
Traveling time of packets is also an important factor to character the network’s performance and here it is defined as the time steps that a packet takes to reach the destination from the source. To guarantee the efficiency of all level-1 time-sensitive packets, of all packets must not exceed a particular explicit value. In Figure 2a, we show the
for two-level packets under the shortest path routing and dynamic source routing. With increasing packet generation rate
,
of level-1 packets under the dynamic source routing is the smallest, while the
of level-1 packets under the shortest path routing(SP) is a little longer than that of DS when
. When
goes beyond 12,
of level-1 packets under the SP is much larger than that of DS.
of level-2 time-insensitive packets under DS is larger than that of level-1, but dramatically shorter than that of level-2 under SP. When
,
of level-2 packets under SP is relatively long, and part level-2 packets on central nodes have fewer opportunities to be forwarded in time. On the contrary,
of level-2 packets under DS can be guaranteed within an upper limitation. In Figure 2b, we choose packet generation rate
at which no network congestion happens under both DS and SP. Again, with increasing
,
of level-1 packets under DS is shorter than that of level-1 packets under SP.
of level-2 packets under SP is the largest under all
. Combined Figure 2a and Figure 2b, dynamic source routing can better guarantee the transmission efficiency of level-1 time-sensitive packets. By bypassing the central nodes with heavy traffic load, traffic capacity of network is enhanced and time-sensitive flows are better supported under our proposed dynamic source routing strategy on two-level flow traffic model.
(a) vs packet generation rate
at
; (b)
vs
at
. Network parameters:
, average degree
. Curves with hollow circles and hollow squares represent
of level-1 under DS and SP respectively, and curves with solid circles and solid squares represent
of level-2 under DS and SP respectively.
Under dynamic source routing strategy, the routing table is computed at each time step and it is time-consuming to compute the average path length of DS. For simplicity, here we compute the average path length by using average hops of all actual packets from their sources to destinations in our simulations.
In Figure 3, we investigate the evolutions of average traveling time , average path length
and average waiting time
with
when
. The relationship of these three metrics is:
. We observe that the average packet traveling time for level-1 packets under DS is the smallest for all
, and the average packet traveling time for level-2 packets under DS is much smaller than that of level-2 packets under SP. In Figure 4, we evaluate the evolutions of these three metrics with
, when
at which the network is in free flow state under both DS and SP routing strategies. Average packet traveling time for level-1 packets under both DS and SP is about the same. Definitely, average path length under the SP is the smallest. Meanwhile, the average path lengths under DS for two levels are different, and level-2’s is a bit longer than level-1’s. Average waiting time has similar evolutions to the average traveling time. Combined Figure 2, Figure 3 and Figure 4 with Figure 1, we can conclude that traffic capacity under DS for two-level flows is higher and time-sensitive packets can be sent to their destinations within limited time. DS on two-level flow traffic model can improve the network performance that the previous routing strategies can’t do, especially guaranteeing the delivery time of time sensitive flows such as telephone communications and video conferences.
(a) vs
; (b)
vs
; (c)
vs
with
. Network parameters:
, average degree
. Curves with hollow circles and hollow squares represent the metric of level-1 under DS and SP respectively, and curves with solid circles and solid squares represent the metric of level-2 under DS and SP respectively.
(a) vs
; (b)
vs
; (c)
vs
. The packet generation rate
. Network parameters:
, average degree
. Curves with hollow circles and hollow squares represent the metric of level-1 under DS and SP respectively, and curves with solid circles and solid squares represent the metric of level-2 under DS and SP respectively.
Traffic load of nodes in the network under different routing strategies is essential, for it reveals the utilization of all queue resources. Here, we evaluate traffic load by measuring the average queue length for two-level flows of all nodes under the two routing strategies. In Figure 5a, at , it is interesting that average traffic load of two levels under DS is smaller than that of SP under all
. With increasing fraction
of level-1 packets, the portion of level-1 packets in the network grows, while the number of level-2 packets decreases. In Figure 5b, average traffic load on each node increases with the packet generation rate
. Level-2’s average traffic load increases sharply while the other three’s grow slowly. When
, time-insensitive packets of level-2 under SP can’t be sent timely and tolerate long transfer time which might be acceptable. The more level-2 packets enter the network, the longer the level-2 queue grows under SP.
(a) vs
with
; (b)
vs
with
. Network parameters:
, average degree
. Curves with hollow circles and hollow squares represent
of level-1 under DS and SP respectively, and curves with solid circles and solid squares represent
of level-2 under DS and SP respectively.
Discussion
With consideration of real applications in which a part of them are time-sensitive and the others are time-insensitive, we proposed a two-level flow traffic model to satisfy different transmission needs. Packets of level-1 were delivered preferentially to level-2 to guarantee the quality of level-1 time-sensitive packet’s transition. To achieve high traffic capacity of network, we propose and investigate a new dynamic source routing. Path of one packet under dynamic source routing was included in the packet and the packet was delivered according to the path. Thus no routing table was used in the process of packet delivering, and it supported the global dynamic routing primely. With higher traffic capacity and supporting diverse traffic flows, our dynamic source routing has a good application perspective in real networks such as Ad-Hoc wireless networks or for next generation networks in future.
The dynamic source routing strategy on two-level flow traffic model expands the possibility of application of the global dynamic routing strategy. To our best knowledge, this work is the first one to differ the time-sensitive and time-insensitive flows to guarantee the real-time applications in complex systems.
Acknowledgments
We acknowledge the high-performance computing platform of Institute of Information Science for basic hardware and software support of simulations of this work.
Author Contributions
Conceived and designed the experiments: ZYJ. Performed the experiments: ZYJ. Analyzed the data: ZYJ MGL. Contributed reagents/materials/analysis tools: ZYJ. Wrote the paper: ZYJ JJW.
References
- 1. Watts DJ, Strogatz SH (1998) Collective dynamics of small-world networks. Nature 393: 440–442.
- 2. Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286: 509–512.
- 3. Albert R, Barabási AL (2002) Statistical mechanics of complex networks. Reviews of modern physics 74: 47.
- 4. Holme P, Kim BJ (2002) Vertex overload breakdown in evolving networks. Physical Review E 65: 066109.
- 5. Zhao L, Park K, Lai YC (2004) Attack vulnerability of scale-free networks due to cascading breakdown. Physical review E 70: 035101.
- 6. Zhao L, Lai YC, Park K, Ye N (2005) Onset of traffic congestion in complex networks. Physical Review E 71: 026125.
- 7. Guimerà R, Díaz-Guilera A, Vega-Redondo F, Cabrales A, Arenas A (2002) Optimal network topologies for local search with congestion. Physical Review Letters 89: 248701.
- 8. Guimera R, Arenas A, Díaz-Guilera A, Giralt F (2002) Dynamical properties of model communication networks. Physical Review E 66: 026704.
- 9. Yan G, Zhou T, Hu B, Fu ZQ, Wang BH (2006) Efficient routing on complex networks. Physical Review E 73: 046108.
- 10. Ling X, Jiang R, Wang X, Hu MB, Wu QS (2008) Traffic of packets with non-homogeneously selected destinations in scale-free network. Physica A: Statistical Mechanics and its Applications 387: 4709–4715.
- 11. Echenique P, Gómez-Gardeñes J, Moreno Y (2004) Improved routing strategies for internet traffic delivery. Physical Review E 70: 056105.
- 12. Kleinberg JM (2000) Navigation in a small world. Nature 406: 845–845.
- 13. Kim BJ, Yoon CN, Han SK, Jeong H (2002) Path finding strategies in scale-free networks. Physical Review E 65: 027103.
- 14. Adamic LA, Lukose RM, Puniyani AR, Huberman BA (2001) Search in power-law networks. Physical review E 64: 046135.
- 15. Herrero CP (2005) Self-avoiding walks on scale-free networks. Physical Review E 71: 016103.
- 16. Yang SJ (2005) Exploring complex networks by walking on them. Physical Review E 71: 016107.
- 17. Tadić B, Thurner S, Rodgers G (2004) Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations. Physical Review E 69: 036102.
- 18. Lawniczak AT, Tang X (2006) Network traffic behaviour near phase transition point. The European Physical Journal B-Condensed Matter and Complex Systems 50: 231–236.
- 19. Wang WX, Wang BH, Yin CY, Xie YB, Zhou T (2006) Traffic dynamics based on local routing protocol on a scale-free network. Physical Review E 73: 026111.
- 20. Wang WX, Yin CY, Yan G, Wang BH (2006) Integrating local static and dynamic information for routing traffic. Physical Review E 74: 016101.
- 21. Yin CY, Wang BH, Wang WX, Zhou T, Yang HJ (2006) Efficient routing on scale-free networks based on local information. Physics letters A 351: 220–224.
- 22. Ling X, Hu MB, Jiang R, Wu QS (2010) Global dynamic routing for scale-free networks. Physical Review E 81: 016113.
- 23. Danila B, Yu Y, Marsh JA, Bassler KE (2006) Optimal transport on complex networks. Physical Review E 74: 046106.
- 24. Danila B, Yu Y, Marsh JA, Bassler KE (2007) Transport optimization on complex networks. Chaos: An Interdisciplinary Journal of Nonlinear Science 17: 026102.
- 25. Jiang ZY, Liang MG (2013) Incremental routing strategy on scale-free networks. Physica A: Statistical Mechanics and its Applications 392: 1894–1901.
- 26. Liu Z, Hu MB, Jiang R, Wang WX, Wu QS (2007) Method to enhance traffic capacity for scale-free networks. Physical Review E 76: 037101.
- 27. Zhang GQ, Wang D, Li GJ (2007) Enhancing the transmission efficiency by edge deletion in scalefree networks. Physical Review E 76: 017101.
- 28. Huang W, Chow TW (2010) An efficient strategy for enhancing traffic capacity by removing links in scale-free networks. Journal of Statistical Mechanics: Theory and Experiment 2010: P01016.
- 29. Hu K, Liu C, Hu T, Tang Y (2010) Enhancing traffic capacity for scale-free networks by the one-way links. Journal of Physics A: Mathematical and Theoretical 43: 175101.
- 30. Huang W, Chow TW (2010) Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network. Chaos: An Interdisciplinary Journal of Nonlinear Science 20: 033123.
- 31. Jiang Z, Liang M, Guo D (2011) Enhancing network performance by edge addition. International Journal of Modern Physics C 22: 1211–1226.
- 32. Fekete A, Vattay G, Kocarev L (2006) Traffic dynamics in scale-free networks. Complexus 3: 97–107.
- 33. Ling X, Hu MB, Du WB, Jiang R, Wu YH, et al. (2010) Bandwidth allocation strategy for traffic systems of scale-free network. Physics Letters A 374: 4825–4830.
- 34. Jiang ZY, Liang MG, Zhang S, Wang SJ, Guo DC (2012) An efficient bandwidth allocation strategy for scale-free networks. International Journal of Modern Physics C 23: 1250065.
- 35. Jiang ZY, Liang MG, Li Q, Guo DC (2013) Optimal dynamic bandwidth allocation for complex networks. Physica A: Statistical Mechanics and its Applications 392: 1256–1262.
- 36. Liu Z, Ma W, Zhang H, Sun Y, Hui PM (2006) An efficient approach of controlling traffic congestion in scale-free networks. Physica A: Statistical Mechanics and its Applications 370: 843–853.
- 37. Zhao L, Lai YC, Park K, Ye N (2005) Onset of traffic congestion in complex networks. Physical Review E 71: 026125.
- 38. Xian-Bin C, Wen-Bo D, Cai-Long C, Jun Z (2011) Effect of adaptive delivery capacity on networked traffic dynamics. Chinese Physics Letters 28: 058902.
- 39. Toroczkai Z, Bassler KE (2004) Network dynamics: Jamming is limited in scale-free systems. Nature 428: 716–716.
- 40. Zhang GQ, Zhou S, Wang D, Yan G, Zhang GQ (2011) Enhancing network transmission capacity by efficiently allocating node capability. Physica A: Statistical Mechanics and its Applications 390: 387–391.
- 41. Arenas A, Dlíaz-Guilera A, Guimera R (2001) Communication in networks with hierarchical branching. Physical Review Letters 86: 3196–3199.