This paper focuses on the fundamental problem of finding disjoint paths that are robust and resilient against channel instability while achieving optimal or near-optimal performance. We formulate and analyze the problem of finding k nodedisjoint paths resilient to c channel accidents in the sense that if any subset of up to c channels are inoperational, at least one path should still be able to deliver packets. We formulate two versions of the resilient multi-path optimization problem using two performance metrics, the sum of cost and the maximal cost of the k paths. Focusing on directed acyclic graphs, we develop approximation algorithms for both problems. We also develop adapted randomized rounding scheme to further trade off the time and space complexities of our approximation algorithm against the optimality guarantee.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Finding Node-disjoint Paths Resilient to Channel Failures in Multi-channel Wireless Networks


    Contributors:
    Li, Guangyu (author) / Chen, Lin (author)


    Publication date :

    2023-10-10


    Size :

    1064876 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Finding Edge-disjoint Paths in Networks: An Ant Colony Optimization Algorithm

    Blesa, M. J. / Blum, C. | British Library Online Contents | 2007


    Robustly disjoint paths with segment routing

    Aubry, François / Vissicchio, Stefano / Bonaventure, Olivier et al. | BASE | 2018

    Free access

    The Complexity of Packing Edge-Disjoint Paths

    Dreier, Jan / Fuchs, Janosch / Hartmann, Tim A. et al. | BASE | 2019

    Free access

    On Routing Disjoint Paths in Bounded Treewidth Graphs

    Ene, Alina / Mnich, Matthias / Pilipczuk, Marcin et al. | BASE | 2016

    Free access

    TWO-CHANNEL COMPARATOR WITHOUT DANGEROUS FAILURES

    POLEVOJ YURIJ IOSIFOVICH | European Patent Office | 2019

    Free access