IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i14p3255-d1201546.html
   My bibliography  Save this article

Dual Protection Routing Trees on Graphs

Author

Listed:
  • Kung-Jui Pai

    (Department of Industrial Engineering and Management, Ming Chi University of Technology, New Taipei City 24301, Taiwan)

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.

Suggested Citation

  • Kung-Jui Pai, 2023. "Dual Protection Routing Trees on Graphs," Mathematics, MDPI, vol. 11(14), pages 1-14, July.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:14:p:3255-:d:1201546
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/14/3255/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/14/3255/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:14:p:3255-:d:1201546. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.