1st International ICST Conference on Communication System Software and MiddleWare

Research Article

Path Diminution is Unavoidable in Node-Disjoint Multipath Routing with Single Route Discovery

  • @INPROCEEDINGS{10.1109/COMSWA.2006.1665210,
        author={Ash Mohammad  Abbas and  Bijendra Nath  Jain},
        title={Path Diminution is Unavoidable in Node-Disjoint Multipath Routing with Single Route Discovery},
        proceedings={1st International ICST Conference on Communication System Software and MiddleWare},
        publisher={IEEE},
        proceedings_a={COMSWARE},
        year={2006},
        month={8},
        keywords={Routing ad hoc networks path diminution node-disjoint multipath routing single route discovery.},
        doi={10.1109/COMSWA.2006.1665210}
    }
    
  • Ash Mohammad Abbas
    Bijendra Nath Jain
    Year: 2006
    Path Diminution is Unavoidable in Node-Disjoint Multipath Routing with Single Route Discovery
    COMSWARE
    IEEE
    DOI: 10.1109/COMSWA.2006.1665210
Ash Mohammad Abbas1,2, Bijendra Nath Jain1,2
  • 1: Department of Computer Science and Engineering, Indian Institute of Technology, Delhi
  • 2: Hauz Khas, New Delhi-110016, India

Abstract

In an ad hoc network, identification of all node-disjoint paths between a given pair of nodes is a challenging task. The phenomena that a protocol is not able to identify all node-disjoint paths that exist between a given pair of nodes is called path diminution. In this paper, we discuss that path diminution is unavoidable when a protocol discovers multiple node-disjoint paths in a single route discovery. We discuss schemes to mitigate path diminution. However, no such scheme is guaranteed to discover all node-disjoint paths that exist between a given pair of nodes. We have proved that one cannot devise an efficient algorithm that is guaranteed to compute all node-disjoint paths between a given pair of nodes in a single route discovery