Probabilistic Study on Node-to-Node Network Routing Path Length
Jianer Chen · Mini-micro Systems · 2004
Based on node failure probability,this paper proposes a new probabilistic analysis method to study the routing path length of network routing algorithms.It used hypercube as our network topology and propose two routing algorithm and strictly analyze their routing path length's conditional expectation.The analysis shows that for very significant node failure probability (can be up to 10%),the length's conditional expectation of a routing path from source node U to the k sub-hypercube of end node V is less than 1.11h is the Hamming distance between node U and node V),which is more less than 2h (2h is our usual result).Based on a new routing algorithm,the paper renews to analyze the routing path length and its conditional expectation.It gets a new expression of routing path length--1.11h-0.11k+2.