Design and Implementation of Peer-to-Peer Service Routing Algorithm

Xiaoyan Gao

Department of Computer Science, North China Institute of Science and Technology, Beijing, China.

DOI: 10.4236/jsea.2015.811054                

Abstract

Due to the lack of QoS (quality of service) guarantee in current Peer-to-Peer services routing network, it is difficult to apply Peer-to-Peer network to business successfully. Therefore, a service guarantee routing model is proposed in this paper, and an ant colony algorithm is designed for this routing model. Finally, the experimental analysis of the Peer-to-Peer services routing algorithm is presented. The experimental result shows the effectiveness of the service routing algorithm.

Keywords

Peer-to-Peer, Services Routing, Ant Colony Algorithm

1. Introduction

Peer-to-Peer (P2P) service routing is an important area of the P2P network. Currently, the P2P routing is divided into the categories of unstructured and structured routing algorithms. Unstructured P2P network is not fixed logical topology of the P2P network. Joining and leaving Nodes affect only the direct neighbors. The message overhead is relatively small. Typical unstructured P2P network routing includes Gnutella, Freenet, APPN, NeuroGrid [1] and so on. Unstructured P2P network routing has been used, but faces low routing efficiency, in particular lack of quality of service guarantees. Structured P2P network routing table (referred to as DHT) is constructed in accordance with Direct Hash Table. Each node has a unique identifier. According to the identifier of the message destination, the node can route messages to the node closest to the node identifier and message identifier. The typical structure of P2P networks includes Chord [2] , CAN [3] , Pastry [4] and Tapestry [5] - [7] . P2P has been applied in other fields of business, finance and tourism. The P2P services a wide range of applications and further development in these areas is limited due to lack of quality of service guarantee. Most of the current P2P lacks consideration of the quality of service. This paper studies the P2P routing algorithm from perspective of quality of service. The proposed algorithm is able to provide guaranteed quality of service routing and promote the development and wide application of the P2P network.

2. P2P Service Routing Problem

For the P2P service routing in this paper, factors affecting the service routing can be considered from the following aspects: the connection bandwidth between network nodes; the maximum bandwidth of node; The session time between nodes. P2P service network routing goal is to establish a service path that meet the above requirements from source node to the destination node, and get the maximum throughput of P2P services along the selected path.

2.1. Define P2P Services Routing Problem

P2P services routing problem can be defined as:, V show nodes set in P2P, E is the corresponding edge between nodes. Every node can join and leave network random, b_ib_j is available bandwidth between i and j, then, , c_ij show the minimum available bandwidth between i and j, a service quality assurance of the P2P services routing goal is to find a path to make P2P services network throughput maximization, and satisfy the following requirements. Select the Maximum bandwidth utilization rate; the effective bandwidth between the nodes is between connection bandwidth and acceptable bandwidth.

2.2. Formalization P2P Services Routing Problems

In a undirected graph, B_ij is bandwidth between the node I and the node j, F_ij show traffic between node I and node j, then defined as follows:

(1)

Assume source s and destination d, , , there are multiple paths between a given source and destination, a collection of all these paths is, P_i is one of path in., B_ij is bandwidth between the node i and the node j, x_ij is binary variables. x_ij = 1, is connected, else is not connected. b_ij is available bandwidth between node I and node j, c_ij is the minimum accepted bandwidth between node i and j.

In summary, the problem can be described as the following:

In this model, the objective function is: the set of multiple paths between a given source and destination, find one of these paths which has maximum utilization of the bandwidth of the path of service.

(2)

3. P2P Service Routing Implementation Process of the Ant Colony Algorithm

Nodes in the P2P service network play an important role in routing. The bandwidth of the node is related to the performance of the entire network, so attributes of high capacity nodes are considered. In this paper, the available bandwidth of nodes is considered and guarantees the available bandwidth of nodes so as to ensure that each service can be achieved availability. First, the P2P service routing model is built, then ant colony algorithm to solve the service routing problems is design.

Ant colony or swarm intelligence algorithm [8] - [10] is an optimization algorithm inspired by the patterns of behavior by the ants to find food, the ant colony algorithm as a heuristic algorithm is to provide a very good network quality of service algorithms, ant colony algorithm has the potential ability in applying to solve the routing problem, artificial ants are probe packets, they will leave artificial pheromone on the path, the transition probability of ants on each route can calculate through the pheromone in the statistics on the path and inspire factor [11] - [13] , after several iterations, the highest pheromone routing is to answer.

The selection probability of ants on each route (i, j) can be described as follows:

As,

(3)

In Equation (3):

shows the k ant the next selection set of paths; show the k ant probability through path (i, j) from i to j, show the pheromone in the path (i, j) at the t time; F_ij show traffic through path (i, j); B_ij is the bandwidth through path (i, j). and show weight in controlling the pheromone and path respectively.

Now show the pheromone in the path (i, j) at the t time, while an t finish one cycle, then the pheromone become as follow:

(4)

In this Equation (4), is constant coefficient between o and 1, show pheromone evaporation between time t and time t plus 1.

(5)

In this equation, is the pheromone variable through path (i, j) between time t and time t plus 1. It can be defined:

(6)

In Equation (6), Q is a constant. It is the pheromone after ant finish one complete path search. L_k is the total path bandwidth utilization of the k ant. It is equal to the sum of the k-th segment of the passed path of the ants bandwidth utilization. If the total bandwidth utilization of the path of the ants is higher, concentration of pheromone is higher by released per unit path. Obviously, the ants will not release pheromone on the path which has never experienced.

Dynamic Ant Colony Algorithm for solving problem as follows:

Global search ability and search speed of the application of ant colony algorithm used to solve the P2P service network routing problem [14] [15] , Specific of ant colony algorithm realization as follows:

Begin

Initialization, the m ants on the starting node s, , k = 1, ∙∙∙, n

(c is a constant)

Loop

For k = 1 to m do

Ant k to determine if the current node i connecting the node has gone through.

Calculate the probability of all nodes are not traversed, and selecting randomly the next node j according to the probability applying for Equation (2), (3); Update the pheromone concentration in the path between nodes m i and j applying for Equation (4), (5) and (6),

If node j is object node t then

Determine the path bandwidth utilization is the largest, if it is the largest path then record the point

The starting node s and destination node t are interchangeable and empty node traversed records

End

If approximate bandwidth utilization is greater than the sum given the current bandwidth utilization

then exit Loop

Else go to Loop

End.

4. Experimental Analysis

Environment of the experiment to build 16 units of the Red Hat Linux operating system on 16 PCs, using Java to design and realization [16] [17] . Waxman topology generation algorithm based on

will generate the network topology. In order to verify the effectiveness of service-based P2P service routing algorithm, randomly selected 16 as an ordinary node. The data communication between nodes used the Java RMI mechanism, synchronization cycle simulation. In each round a loop, each node is read from its input queue, and then processed according to the specified routing rules.

P2P service routing algorithm, assume, , , , ants number, ,. All nodes every two seconds sending service advertising messages in the two systems generate network congestion, because the experimental derivation of the LAN environment, the transmission time between two nodes is very short, not enough to reflect the real Internet environment, so each times send an additional 10 seconds of delay between each two nodes.

From Figure 1, we can see that service P2P service network routing ant colony algorithm is less than Dijkstra algorithm caused by the bottleneck at any one time interval. Therefore in the same network conditions, Ant algorithm has less router price, has better performance than the Dijkstra algorithm.

The convergence rate in different network scale under the conditions of two kinds of algorithms, it can be seen from Figure 2, with the increase of network nodes, Ant algorithm has faster convergence speed, this is because with the increasing scale of the network, the algorithm of feasible solution space increased, if the evolutionary algorithm cannot effectively reduce the solution space, will not improve the convergence rate of the algorithm. The Ant algorithm uses the idea of simulated annealing, so as to ensure the convergence of feasible solution, and ultimately accelerate the iteration to find the optimal solution (or approximate optimal solution) speed. Dijkstra algorithm is able to find the shortest path from a node to another node of the graph, after Dijkstra algorithm once, we can get the shortest path from start to within its searching all nodes, and its time complexity

Figure 1. The comparison of router price of the two algorithms.

Figure 2. The iterative time with the network nodes vary.

is (n is nodes in graph). The main concern is the shortest path between two specific nodes rather than the point of origin to other points in the calculation of network routing. The characteristic of the Ant colony algorithm is an enhanced learning system, distributed computing features and has a strong robustness. Ant colony algorithm is very suitable for solving complex combinatorial optimization problems, the P2P service network routing problem is a combinatorial optimization problem, so the Ant colony algorithm to solve the P2P service network routing problems. Using the ant colony algorithm and Dijkstra algorithm respectively solve P2P service network routing problems. The experimental results show that the Ant colony algorithm is relatively fast to find the approximate route, and the system copies the information less, the reason is that the Ant colony algorithm is a simulation of evolutionary algorithms, ant colony algorithm with groups of co-operation, positive feedback and distributed computing features and many main Agent (referred to here the main body of the ant) can be better to complete the task of optimizing collaboration between groups of cooperation; positive feedback makes the algorithm quickly find better solutions; it is easy to achieve parallelism for distributed computing algorithm.

Acknowledgements

This work was financially supported by the Hebei province science and technology research project (No. Z2014038). The work was supported by the Fundamental Research Funds for the Central Universities (3142014125, 3142015022, 3142013098, and 3142013070).

Gaoxiao Yan, associate professor, Dr., majors in communication and information system. Research directions include the computer network and the network security. She was a visiting scholar at Queen’s University in Canada.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Seet, B.C. (2009) Mobile Peer-to-Peer Computing for Next Generation Distributed Environments: Advancing Conceptual and Algorithmic Applications. IGI Global Press, New York. http://dx.doi.org/10.4018/978-1-60566-715-7
[2]	Psillassa, B., Yawut, C. and Dhaou, R. (2011) Network Awareness and Dynamic Routing: The Ad Hoc Network Case. Computer Networks, 55, 2315-2328.
[3]	Zhao, B., Kubiatowicz, J. and Joseph, A. (2001) Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing. Technical Report UCB/CSD-01-1141, Computer Science Division, University of California, Berkeley, Berkeley, 106-115.
[4]	Maymounkov, P. and Kademlia, M.D. (2002) A Peer-to-Peer Information System Based on the XOR Metric. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS 2002), Cambridge, 7-8 March 2002, 53-65. http://dx.doi.org/10.1007/3-540-45748-8_5
[5]	Karger, D.R., Lehman, E., Leighton, T., Levine, M., Lewin, D. and Panigrahy, R. (1997) Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the Worldwide Web. ACM Symposium on Theory of Computing, 5, 654-663. http://dx.doi.org/10.1145/258533.258660
[6]	Gambardella, L.M. and Dorigo, M. (1995) Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Proceedings of the 12th International Conference on Machine Learning, Tahoe City, 9-12 July 1995, 252-260. http://dx.doi.org/10.1016/b978-1-55860-377-6.50039-6
[7]	Boschetti, M., Jelasity, M. and Maniezzo, V. (2004) A Local Approach to Membership Overlay Design. Working Paper, Department of Computer Science, 16, 250-360
[8]	Tsai, C.F. and Tsai, C.W. (2002) A New Approach for Solving Large Traveling Salesman Problem Using Evolution Ant Rules. Proceedings of the 2002 International Joint Conference on Neural Networks, 2, 1540-1545.
[9]	Lv, K.C. (1999) Single Objective, Multi-Objective and Integer Programming. Tsinghua University Press, Beijing.
[10]	Lei, D.M. and Yan, X.P. (2009) Multi-Objective Intelligent Optimization Algorithm and Its Application. Science Press, Beijing.
[11]	Wu, J., Cheng, B., Yuen, C., Cheung, N.-M. and Chen, J. (2015) Trading Delay for Distortion in One-Way Video Communication over the Internet. IEEE Transactions on Circuits and Systems for Video Technology, PP, 1. http://dx.doi.org/10.1109/TCSVT.2015.2412774
[12]	Wu, J., Cheng, B., Yuen, C., Shang, Y. and Chen, J. (2015) Distortion-Aware Concurrent Multipath Transfer for Mobile Video Streaming in Heterogeneous Wireless Networks. IEEE Transactions on Mobile Computing, 14, 688-701. http://dx.doi.org/10.1109/TMC.2014.2334592
[13]	Wu, J., Yuen, C., Cheung, N.-M. and Chen, J. (2015) Delay-Constrained High Definition Video Transmission in Heterogeneous Wireless Networks with Multi-homed Terminals. IEEE Transactions on Mobile Computing, PP, 1. http://dx.doi.org/10.1109/TMC.2015.2426710
[14]	Wu, J., Tian, Y., Cheng, B. and Shang, Y. (2013) Comprehensively Context-Aware Approach to Guarantee Multimedia Conferencing Services. China Communications, 10, 53-64. http://dx.doi.org/10.1109/CC.2013.6623503
[15]	Wu, J., Yuen, C., Cheng, B., Shang, Y. and Chen, J. (2014) Goodput-Aware Load Distribution for Real-Time Traffic over Multipath Networks. IEEE Transactions on Parallel and Distributed Systems, 26, 2286-2299. http://dx.doi.org/10.1109/TPDS.2014.2347031
[16]	Wu, J., Yuen, C., Wang, M. and Chen, J. (2015) Content-Aware Concurrent Multipath Transfer for High-Definition Video Streaming over Heterogeneous Wireless Networks. IEEE Transactions on Parallel and Distributed Systems, PP, 1. http://dx.doi.org/10.1109/TPDS.2015.2416736
[17]	Wang, X. and Cui, P.Y. (2005) New Method Based on Ant Colony Algorithm for Path Planning and Simulation. Computer Simulation, 22, 0060.