Bufferless transmission in complex networks
Bufferless transmission in complex networks
Complex bufferless networks such as one-chip networks and optical burst switching networks haven't been paid enough attention in network science. In complex bufferless networks, the store and forward mechanism is not applicable, since the network nodes are not allowed to buffer data packets. In this paper, we study the data transmission process in complex bufferless networks from the perspective of network science. Specifically, we use the Price model to generate the underlying network topological structures. We propose a delivery queue based deflection mechanism, which accompanies the efficient routing protocol, to transmit data packets in bufferless networks. We investigate the average deflection times, packets loss rate, average arrival time, and how the network topological structure and some other factors affect these transmission performances. Our work provides some clues for the architecture and routing design of bufferless networks.
INTRODUCTION
NOWADAYS, we build a lot of communication networks according to our needs with advanced technologies. Based on the buffer availability at network nodes, these communication networks, and bufferless communication networks[1]. The former includes the Internet, mobile communication networks, sensro networks, mobile ad hoc networks, and so on. The latter includes the one-chip communication networks [2],[3], optical burst switching network [4], [5], etc. Information transmission is one of the fundamental functions of all these complex communication networks. Different types of communication networks have their own information transmission mechanism. For the buffer-based communication networks, they use the store and forward mechanism [6],[7]. When the traffic flow is large, nodes can not manage all their traffic load due to limited processing capacity, and thus some data packets will be stored in node buffers for subsequent forwarding. This kind of store and forward mechanism need lots of network resources and consumes plenty of node energy to support large traffic and high reliable data communications, more suitable for large communication networks do not adopt the store and bufferless communication networks do not adopt the store and forward mechanism, since they have energy and resource constraints and real-time transmission requirement. Instead, they usually use static routing protocols combined with random deflection mechanism for data transmission [8],[9]. In this case, data packets are transmitted with a given static routing protocol with priority. This will cause the packets compete for the port forwarding, since the node port forwarding capacity is limited. Failed packets are forwarded from other free ports according to the given random deflection mechanism. If all node ports are bury, the failed packets are discarded.
Network science developed rapidly in the past decade, and relevant theories have been applied to the communication networks[10]. However, most work is about the buffer-based complex networks. Researchers were dedicated to improving the network transmission capacity of buffer-based complex networks based on novel strategies [11],[12],[13],[14],[15], which can be basically classified into three categories. The first category is about optimizing the netowrk topologies. Liuet al.[16] pointed out that removign some links between the core nodes can effectively make the data flow avoid the core nodes, thereby reducing traffic congestion. Zhang et al.[17] found that deleting some links between large-betweenness nodes can also rduce the traffic congestion. Huang et al. [18] further improved the above two kindsd of link optimization strategies by defining a node-dfference index. Later, they further improved the network capacity by adding some links between distant nodes and between the neighbors of large degree nodes [19].
The second category is to optimize the network resrouces. Kim et al.[20] studied the relationship between the delivery capablity and the laod fo nodes in different networks. They found that the node's delivery capability in the real systems is not fully utilized due to the fluctuation of the network data traffic. This problem is more serious among nodes of small delivery capability. Liu et al. [21] assumed that the node's capabilities of generating and delivering packets are related to the node degree, and further studied their impact on traffic congestion. Gong et al [22] found tha there is a maximum network capacity when the network structure and routing strategy are give, which is inversely proportional to the average transmission path length. Ling et al. [23] considered both the node's delivery capability and link bandwidth constraints, and they found that allocating the resources based on the algorithmic betweenness of nodes can achieve the maximum network capacity. Liu et al [24] considered the heterogeneous network capacity. Liu et al.[24] considered the heterogeneous data flow generated by the nodes. and optimized the network flow and the node delivery capability to maximize the network utility.
The optimization of network structure or network resource is related to network hardware, and thus it has high cost and sometimes it is not feasible in real applications. The third category is the optimization of entwork routing protocols. This kind of work usually involves only the network software, which is relatively simple to implement and the cost is relatively small. For exmaple, Yan et al [25] proposed an efficient routing algorithm based on the degree of onpath nodes with a control parameter. Du et al [26] further considered the forwarding priority of the packet based on the global routing algorithm proposed by Yan. Wang et al. [27] proposed a random forwarding strategy based on neighbor node degree. They further considered the load information and proposed a local dynamic routing strategy [28], Ling et al. [29] proposed a global dyanmic routing protocol which selects the optimal path of the smallest path load. Wu et al.[30] proposed a routing strategy based on both the neighbor node degree and the shortest path length information. Yang et al. [31] proposed an adptive routing stratey based on node distnace and node load. the above-mentioned routing algorithms can effectively improve the network capacity [36],[37]. Form the angle of network science, we study the data transmission process in bufferless communication networks. Specifically, We dedicate to applying complex network models and routing strategies proposed for general complex networks to bufferless communication networks. We propose a new random deflection strategy to deal with the forwarding competition problem in bufferless communication networks. Through simulation, we investigate how various factors influence transmission performances.
2. THE NETWORK MODEL
We use Price model [38] to generate the underlying network topological structures. Price model is a typical model to generate scale-free networks. Compared to BA model [39], Price model can adjust the power-law parameter, thus adapting the node degree distribution. the steps of fast algorithms of Price model are given as follows:
(i) Initially, we generate a fully connected directed graph of m0 nodes. Then, we put the labels of nodes that each link points to into an array Arr.
(ii) We set a Parameter P. For t = 1,2 we take following actions: (1) We generate a random number r (2) IF r<P, we randomly select an item from Arr: (3) if r>= P, we randomly select a node; (4) We do step(1)-(3) m times (maybe more times to avoid repeated choices), and get m links of the new node added at time t. We put the labels of the m selected nodes into Arr. Note that for put the labels of the m selected nodes into Arr. Note that for a new node, the m links should point to m different nodes.
Finally, we obtain an undirected scale-free network with N nodes by ignoring the directions of all links. The average node degree is 2m. the power-law parameter is If we set P = 0.5, then R=3, and Price model degenerates into BA model.
3. DATA TRANSMISSION MODEL AND PERFORMANCES
In buffer-based communication netowrks, non-sent packets will be stored in the buffers at the nodes. In bufferless communication networks, all data packets should be forwarded at each time step. Packets are not allowed to waiting at the nodes. One the other hand, there is a delivery queue at each node. The delivery queue is used to store the packets, which will be sent at the current time step. At the end of each tiem step, the delivery queue is empty.
A. Transmission model
We study the data transmission process in bufferless entworks. In our model, each node generates the data packets with rate p. For example, p = 1,2 means that each node generates one packet withprobability I and another one with probability 0.3 at each tiem step. the destination of each packet is randomly chosen among all the nodes except the source node. The size of the delivery queue is equal to the delivery capability of node. For simplification purpose, we assume that node i can at most deliver C*k(i) packets at each time step, where C is the node delivery coefficient and k(i) is the degree of node i. Note that the queue is for storing the received packets and the generated packets. When the queue is full, the node stops generating packets. If the current node is the destination of the packet, the packet willl be discarded from the queue immediately. We apply the efficient routing protocol [25] to our data transmission model. The basic idea of the efficient routing protocol is as follows: a path from node a to node b can be denoted as P(a->b) where vi is the i+1th node in the path. the transmission cost of this path is defined as follows [25]. to our data transmission model. The basic idea of the efficient routing protocol is as follows: a path from node a to node b can be denoted as P(a->b)= a v0, v1,vn-1 vn = b where vi is the i+1th node in the path. the transmission cost of this path is defined as follows [25].
where a is a tunable parameter. For all the path from a to be, the one with the amallest transmission cost is chosen as the optimal transmission path. If there is more than one optimal path, we randomly choose one as the transmission path. Obiously, the optimal tranmission path is determined by the control parameter a When a = 0, the efficient routing protocol degenerates into the shortest path protocol.
For bufferless data transmission, we usually need certain deflection mechanism to deal with the forwarding competition. Failed packets will be delivered from other node ports instead of the port determined by the static routing protocol. If there are no free port, the failed packets will be discarded Here, we propose a delivery queue based deflection mechanism.
Specifically, a packet will check the delivery queue of the next-hop node given by the efficient routing before being sent. If the queue is full, the packet will randomly select another neighbor node of the current node and check the queue status of the neighbor node. If the queue is also full, the packet will do another selection until finding a not-full neighbor node. If all neighbors' queue is full, the packet will be discarded. This deflection mechanism accompany the efficient routing protocol to deliver the data packets in the model.
B. Transmission pefromances
For buffer-based communication networks, the network capacity is the first concern, which measures the maximum allowed data packets generation rate of nodes under free flow state. However, for bufferless communication networks, packet loss rate and deflection times are more important than network capacity. Here we define the packet loss rate to be the ratio between the number of discarded packets (The arrival packets are not included.) and the number of generated packets for large time period T, which is given as follows:
When nd is the total delfection times of all nodes during time period T. Also we measure the average arrival time of packets T, which is the average number of transmission steps for a packet from the source to the destination. Through these three metrics, we can evaluate the transmission model, the performance of the routing algorithms, and hwo the network topological strucutre affects the data transmission.
4. SIMULATION RESULTS
In this part, we investigate the transmission peformances of our bufferless transmisssion model by simulation. The aim is to demonstrate how various factor affect the transmission performances. In the simulation experiments, we vary one particular parameter by keeping all the other parameter constant. Also, we let our model run a long time (T=1000) in order to obtain a stable traffic flow.
First, we study how the packet generation rate p affects the transmission performances. In the experiments, we set network size N=1000, average node degree(k)=4, powerlaw parameter r = 3, node delivery coefficient C = 2, and routing control parameter a = 1. The simulation results are presenting in Fig 1. where each data point is the average of 100 independent runs. In Fig 1(a), we see that when the packet generation rate r is very small. the average deflection times w is zero. After rho exceeds the critical value 0.2 w goes up absruptly and then reaches the peak, and then goes down a little bit, and finally converges. When the packet generation rate is very small, there is no packet forwarding competition. and all the packets are transmitted with the efficient routing protocol to the destinations. Thus, the average deflection times are zero, When the packet generation rate exceeds the critical value, the packet forwarding competition appears and becomes more serious with the increase of the packet generation rate. More and more packets are deflected to the non-full neighbors of current nodes. Thus, the average deflection times increase. When the packet generation rate is large eough. there may not be any non-full neighbors of the current nodes, thus some packets are discarded directly instead of been defelcted and the average deflection times decrease. In Fig 1(b), when the packet generation rate rho is very small, the packet loss rate is zero. After rho exceeds the critical value 0.2, w goes up absruptly and then reaches the peak, and then goes down a little bit, and finally converages. When the packet generation rate is very small. there is no packet forwarding competition, and all the packets are transmitted with the efficient routing protocol to the destinations. Thus, the average defelction times are zero. When the packet generation rate exceeds the critical value. the packet forwarding competition appears and becomes more serious with the increase of the packet generation rate exceeds the nodes are full appears, and this leads to the packet loss. This problem becomes more serious with the increase of the packet generation rate. In Fig. 1(c), we see that the average arrival time T goes up and then goes down with the increase of the packet generation rate rho. this is because the increase of the average delfection times generally results in the increase of the average arrival time converge finally.
Then, we investigate how the node delivery capability affects the transmission performances. Note that we defined the node delivery capability to be proportional to the node degree in the above. In the experiments, we vary the node delivery coefficient to change the node delivery capability. The relevant parameters are as follows: network size N = 1000, average node degree (k) = 4, power-law parameter r = 3, packet generation rate rho = 2, and routing control parameter a = 1, The simulation results are shown in Fig.2, where each data point is the average of 100 independent runs. In Fig. 2(a). we see that with the increase of the node delivery coefficient C, the average deflection times w goes up first, and then reaches the peak, and then goes down and finally becomes zeo. On one hand, the increase of node delivery capbility increases the capability of receiving and forwarding the deflected packets, which results in the increase of average deflection times. On the other hand, the increase of average deflection times. On the other hand, the increase of node delivery capability decreases the number of packets needed to be deflected. Therefore, the average deflection times decrease until becoming zero. there contrary effects lead to a maximum average deflection times. In Fig. 2(b), we see that the packet loss rate decreases until becoming zero whe nthe node delivery coefficient C inreases, the reason of which is obvious. In Fig. 2(c), we see that the average arrival time Ta increases with the node delivery coefficient C first, and then decreases until becoming 6, which is the average transmission path length of the efficient routing protocol. there is also a maximum average arrival time. The increase of average deflection times results in the increase of the average arrival time. however, when the node delivery capability is large enough, the number of deflected packets decrease until becoming zero, which results in the decrease of the average arrival time.
Next, we study the incluence of network topological structures on the transmission performances. First, we vary the average node degree to see the change of the relavant transmission performances. In the experiements, we set network size N = 1000, power-law parameter r = 3, packet generation rate rho = 2, node delivery coefficient C = 1, and routing control parameter a = 1. The simulation results are shown in Fig.3, where each data point is the average of 100 independent runs. We see that the variation trend in the curves of the average deflection times w, the packet loss rate r, and the average arrival tiem t is similar to that in Fig. 2. In fact, the increase of average node degree also increases the node delivery capability according to our definition of node degree, which facilitates the data transmission. this is why the curves of Fig. 3 change more intensely than Fig. 2. Then ,we vary the pwoer-law parameter r to change the degree of network heterogeneity, and study how the transmission performances change. the relevant parameters are as follows: network size N = average node degree (k)=4, packet generation rate rho = 2, node delivery coefficint C = 1, and routing control parameter a 1. The simulation results are shown in Fig. 4, each data point is the average of 100 independent runs. In Fig. 4(a), we see that the deflection tiems w increases with power-law parameter r first, andthen decreases slightly. the larger the r, the more homogeneous the node degree distribution is. Homogeneous node degree distribution generally makes the neighbor nodes more capable to deflect the packets. Moreover, the average transmission path becomes longer with the increase of the homogeneity of node degree distribution, which means the probability of being deflected increases. These effects lead to the increase of the average deflectio ntimes. On the other hand when the node degree distribution becomes even, the packets will be distributed more even and the forwarding competition becomes less, and this is why the average deflection times decrease. In Fig. 4(b), we see that the packet loss rate r goes up with the increase of power-law parameter R, and then goes down.
The average trans mission path becomes longer when the node degree distribution becomes more even, which results in the increase of packet loss rate. On the other side, the forwarding competition becomes less when the node degree distribution becomes more evenly, which results in less packet loss. In Fig. 4(c), we see that the average arrival tiem Ta increases first with the power-law parameter r, and then decreases. The increase of both the average path length and the average deflection times results in the increase of the average arrival time. Accordingly, the decrease of the average deflection times results in the decrease of the average arrival time. Next, we vary the number of nodes while fixing the other parameters to study the change of the transmission performances. In the experiments, we set average node degree (k) = 4, pwoer law parameter r = 3, packet generation rate rho = 1, packet delivery coefficient C = 2, and the routing control parameter a = 1. The simulation results are given in Fig 5, where each dat apoint is the average of 100 independent runs. From Fig. 5, we see that all the tree performances w, r, and Ta increase with the number of nodes N. Moreover, the average transmission path length increases with the number of nodes. All these reasons lead to the deterioration of the transmission performances.
Finally, we study ow the routing strategy affects the transmission performances. In the experiments, we vary the routing control parameter a while fixing the other parameter, which are network size N = 1000, average node degree (k) = 4, power-law parameter r = 3, packet generation rate rho, node delivery coefficient C = 1. the simulation result are given in Fig. 6, where each data point is the average of 100 independent runs. From Fig. 6, we see that the three transmission performances W r and Ta have the same varying trend. They first goes down with the increase of the routing control parameter A, and then goes up. there is an optimal routing control parameter around 0.4 which corresponds to the minimum w, r and Ta A = 0.4 means the packets are prone to pass through small-degree nodes in order to achieve good trans mission performances. Also, the shortest path routing protocol(corresponding to a = 0 in the efficient routing protocol), commonly used in the bufferless communication networks, is not the optiaml choice. Note that the optiaml routing control parameter is dependent on the specific experiemntal conditions. As shown in Fig. 6(c), the optimal routing control parameter is different for differnet values fo power-law parameter.
5. CONCLUSION
In summary, we study the data transmission in bufferless communication networks fromthe perspective of network science. Instead of networks from the perspective of network science. Instead of network capacity well discussed in literature. We focuse on the transmission performances such as the deflection times and packet loss rate, since these metrics are the main concerns for the buffeerless communication network. We apply the Price model and the efficient routing protocol to the context of bufferless data transmission. We propose a delivery queue based deflection mechanism to deal with the packet forwarding competition. We find that the effcts of factors, such as the packet generation rate, node delivery capability, average node degree, and degree distribution, on the transmission performances are in general non-monotonic. As for th eefficient routing protocol, there is optimal control parameter dependent on the network conditions, leading to the optiaml transmission performances. Our work is a preliminary effort to apply theories and tools from network science to bufferless communication networks. We believe ti will help to build the network architecture and network routing protocol in the burfferless communication sysstems.