Comparison on Routing Processing Performance between Shortest Paths Tree (SPT) and Minimum Spanning Tree (MST)

Santi Pattanavichai

doi:10.15866/irecos.v17i2.22439

Comparison on Routing Processing Performance between Shortest Paths Tree (SPT) and Minimum Spanning Tree (MST)

Santi Pattanavichai^(1*)

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/irecos.v17i2.22439

Abstract

This study’s objective is to assess the performance of routing processing between Shortest Paths Tree (SPT) and Minimum Spanning Tree (MST). In this paper we propose and create software to calculate the efficiency path of routing processing in the network. Extensive simulations are being carried out with two different algorithms specific for Dijkistra’s algorithm and Kruskal’s algorithm. The network loads in the performance plots are characterized by two important parameters (a number of vertices) - 7 nodes and 10 nodes, more vertices could show good performance in the simulation results and showed that the performance of Kruskal’s algorithm is better than Dijkistra’s algorithm when the network loads are increased from 7 nodes to 10 nodes. In this simulation, Because of the total cost of distance matrix for Kruskal is less than Dijkistra when the number of routers or nodes is increased from 7 nodes to 10 nodes. This software namely Network Aids Design (NAD), is useful for calculation about the performance of routing processing in the network.
Copyright © 2022 Praise Worthy Prize - All rights reserved.

Keywords

Routing Process; Shortest Paths Tree (SPT); Minimum Spanning Tree (MST); Dijkistra’s Algorithm; Kruskal’s Algorithm and Prim's Algorithm

Full Text:

PDF

References

S. Mu, T. Univ, X. Zhang, N. Zhang, J. Lu, IP routing processing with graphic processors, Proceeding of Design, Automation & Test in Europe Conference & Exhibition (page: 93 - 98, Year of Publication: 2010 ISBN: 978-1-4244-7054-9).

S. C. Wirasinghe, U. Vandebona, Route layout analysis for express buses, Transportation Research Part C, Elsevier, pp. 374-385, 2010, doi:10.1016/j.trc.2010.05.021.
https://doi.org/10.1016/j.trc.2010.05.021

M. Steenstrup, Routing in communications networks, Prentice Hall International (UK) Ltd. Hertfordshire, UK, UK, 1995.

Hadas, R. L., A derivation-first approach to teaching algorithms, Proceedings of the 44th ACM technical symposium on Computer science education (page: 573-578, Year of Publication: 2013 ISBN: 978-1-4503-1868-6).

F. Huang, P. Gao, Y. Wang, Comparison of Prim and Kruskal on Shanghai and Shenzhen 300 Index hierarchical structure tree, Proceedings of International Conference on Web Information Systems and Mining IEEE (page: 237-241, Year of Publication: 2009 ISBN: 978-0-7695-3817-4).
https://doi.org/10.1109/WISM.2009.56

M.M. Syslo, N. Deo, J.S. Kowalick, Discrete Optimization Algorithms with Pascal Programs, Prentice-Hall Inc, Englewood Cliffs, New Jersey, 1983.

A. Limaiem, H. A. ElMaraghy, Automatic Path Planning for Coordinate Measuring Machines, Proceedings of the 1998 IEEE International Conference on Robotics & Automation Leuven, Belgiu, (page: 887-892, Year of Publication: 1998 ISSN :1050-4729).

G. Zhou, M. Gen, Genetic algorithm approach on multi-criteria minimum spanning tree problem, European Journal of Operational Research, Vol. 114, n. 1,pp. 141-152, 1999.
https://doi.org/10.1016/S0377-2217(98)00016-2

J. Marte, The expected complexity of Prim's minimum spanning tree algorithm, Information Processing Letters, Vol. 81, n. 4, pp. 197- 201, 2002.
https://doi.org/10.1016/S0020-0190(01)00220-4

Y. G. Huib, Z. C. Guang, An algorithm for clustering gene expression data using minimum spanning tree, Journal of Computer Research and Development, Vol. 40, n. 10, pp. 1431-1435, 2003.

H. Y., Xu De, D. G. Zhong, Using MST in handwritten Chinese characters segmentation. Journal of Software, Vol. 17, n. 3, pp. 403-409, 2006.
https://doi.org/10.1360/jos170403

T.H. Cormen, C.E. Leirson, R.L. Rivest, Introduction to Algorithms. (MIT Press, 1997).

B. Awerbuch, I. Cidon, S. Kutten, Optimal Maintenance of a Spanning Tree, Journal of the ACM (JACM), Vol. 55, n. 40, pp. 18:1-18:45, 2008.
https://doi.org/10.1145/1391289.1391292

J. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc, Vol. 7, pp. 48-50, 1956.
https://doi.org/10.1090/S0002-9939-1956-0078686-7

R. C. Prim, Shortest connection networks and some generalizations, Bell Syst Technol J, Vol. 36, pp. 1389-1401, 1957.
https://doi.org/10.1002/j.1538-7305.1957.tb01515.x

L. Lorenzo, S. L. Freire, A characterization of Kruskal sharing rule for minimum cost spanning tree problems, International Journal of Games Theory, Springer, Vol. 38, n. 1, pp. 107-126, 2009.
https://doi.org/10.1007/s00182-008-0147-0

V. Jarník, O jistém, About a certain minimal problem, Czech mathematician, Vol. 6, pp 57-63, 1930.

E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematlk, Vol. 1, pp. 269-271, 1959.
https://doi.org/10.1007/BF01386390

T. chuanyan, C. xiaohe, Y. pingli, Prim algorithm to set up communication network system, Computer simulation, Vol. 25, pp. 204-207, 2008.

S. Sowsanit, S. Pattanavichai, Analysis and Simulations of Routing Protocols with Two Different Algorithms, In Proceedings of International Conference on ICT and Knowledge Engineering (page: 60 - 65, Year of Publication: 2014 ISBN:978-1-4799-8025-3).

Refbacks

There are currently no refbacks.

Username
Password
Remember me