Improved HyperD Routing Query Algorithm
Under Different Strategies
Xiaoyu Tao, Bo Ning
(&)
, Haowen Wan, and Jianfei Long
Dalian Maritime University, Dalian 116026, China
ningbo@dlmu.edu.cn
Abstract. A hypercube labeling model HyperD was introduced to solve the
problem of excessive bandwidth consumption and long query time between
various nodes. By analyzing and adopting different strategies to improve the
routing query algorithm of HyperD, a relatively more efficient routing query
algorithm is proposed, which reduces the cost of communication and accelerates
the data transmission between nodes. In order to verify the effectiveness of the
algorithm, experiments were performed on randomly selected HyperD networks
of various sizes. The improved routing algorithm was compared with the known
routing algorithms, the results show that the improved algorithm is more efficient, and it can find the optimal solution in valid time.
Keywords: Bandwidth consumption Á Routing query algorithm Á HyperD
1 Introduction
Reducing unnecessary message transmission and the overall bandwidth utilization in
P2P networks is a very interesting issue [1–4]. Toce et al. [5–7] used hypercube in
dynamic label mode (HyperD) to prove that the label mode can reduce the bandwidth
utilization in the network under certain conditions. Compared with the traditional
Dijkstra algorithm [8–10], the HyperDRouter algorithm given by Andi Toce et al.
greatly reduces the search time, but it cannot find a better path in a valid time for noncomplete hypercube cases. This paper continuously improved the routing query
algorithm with different strategies. We, respectively, proposed MNR, MMNR, and
MPPR algorithm. Then, we compared and analyzed the three algorithms with the
existing Dijkstra algorithm and the HyperDRouter algorithm given. The results showed
that the MPPR algorithm was the best overall, especially in the case of a high sparse
rate.
2 Routing Query Algorithm
In routing algorithm HyperDRouter, the path between two nodes is determined by the
Hamming distance between their labels and the path of any intermediate nodes [8, 11].
The time complexity is close to O k
2
ð Þ, and k is the dimension. The followings are the
improved routing algorithm of HyperD with different strategies, which can find the
optimal solution in an effective time.
© Springer Nature Singapore Pte Ltd. 2020
Q. Liang et al. (Eds.): Artificial Intelligence in China, LNEE 572, pp. 435–441, 2020.
https://doi.org/10.1007/978-981-15-0187-6_52
Under Different Strategies
Xiaoyu Tao, Bo Ning
(&)
, Haowen Wan, and Jianfei Long
Dalian Maritime University, Dalian 116026, China
ningbo@dlmu.edu.cn
Abstract. A hypercube labeling model HyperD was introduced to solve the
problem of excessive bandwidth consumption and long query time between
various nodes. By analyzing and adopting different strategies to improve the
routing query algorithm of HyperD, a relatively more efficient routing query
algorithm is proposed, which reduces the cost of communication and accelerates
the data transmission between nodes. In order to verify the effectiveness of the
algorithm, experiments were performed on randomly selected HyperD networks
of various sizes. The improved routing algorithm was compared with the known
routing algorithms, the results show that the improved algorithm is more efficient, and it can find the optimal solution in valid time.
Keywords: Bandwidth consumption Á Routing query algorithm Á HyperD
1 Introduction
Reducing unnecessary message transmission and the overall bandwidth utilization in
P2P networks is a very interesting issue [1–4]. Toce et al. [5–7] used hypercube in
dynamic label mode (HyperD) to prove that the label mode can reduce the bandwidth
utilization in the network under certain conditions. Compared with the traditional
Dijkstra algorithm [8–10], the HyperDRouter algorithm given by Andi Toce et al.
greatly reduces the search time, but it cannot find a better path in a valid time for noncomplete hypercube cases. This paper continuously improved the routing query
algorithm with different strategies. We, respectively, proposed MNR, MMNR, and
MPPR algorithm. Then, we compared and analyzed the three algorithms with the
existing Dijkstra algorithm and the HyperDRouter algorithm given. The results showed
that the MPPR algorithm was the best overall, especially in the case of a high sparse
rate.
2 Routing Query Algorithm
In routing algorithm HyperDRouter, the path between two nodes is determined by the
Hamming distance between their labels and the path of any intermediate nodes [8, 11].
The time complexity is close to O k
2
ð Þ, and k is the dimension. The followings are the
improved routing algorithm of HyperD with different strategies, which can find the
optimal solution in an effective time.
© Springer Nature Singapore Pte Ltd. 2020
Q. Liang et al. (Eds.): Artificial Intelligence in China, LNEE 572, pp. 435–441, 2020.
https://doi.org/10.1007/978-981-15-0187-6_52