Dual Protection Routing Trees on Graphs

Kung-Jui Pai ()
Additional contact information
Kung-Jui Pai: Department of Industrial Engineering and Management, Ming Chi University of Technology, New Taipei City 24301, Taiwan

Mathematics, 2023, vol. 11, issue 14, 1-14

Abstract: In IP networks, packet forwarding is destination-based and hop-by-hop, and routes are built as needed. Kwong et al. introduced a protection routing in which packet delivery to the destination node can proceed uninterrupted in the event of any single node or link failure. He then showed that “whether there is a protection routing to the destination” is NP-complete. Tapolcai found that two completely independent spanning trees, abbreviated as CISTs, can be used to configure the protection routing. In this paper, we proposed dual protection routing trees, denoted as dual-PRTs to replace CISTs, which are less restrictive than CISTs. Next, we proposed a transformation algorithm that uses dual-PRTs to configure the protection routing. Taking complete graphs K n , complete bipartite graphs K m,n , hypercubes Q n , and locally twisted cubes LTQ n as examples, we provided a recursive method to construct dual-PRTs on them. This article showed that there are no two CISTs on K 3,3 , Q 3 , and LTQ 3 , but there exist dual-PRTs that can be used to configure the protection routing. As shown in the performance evaluation of simulation results, for both Q n and LTQ n , we get the average path length of protection routing configured by dual-PRTs is shorter than that by two CISTs.

Keywords: protection routing; completely independent spanning trees; dual protection routing trees; complete graphs; complete bipartite graphs; hypercubes; locally twisted cubes (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/14/3255/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/14/3255/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:14:p:3255-:d:1201546

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().