A delay estimation approach in stochastic overlay networks

Overlay networks are resilient in transferring data through intermediate nodes. The dynamic stochastic shortest path (DSSP) can be utilized in overlay networks to find the optimized relay paths; however, DSSP depends on the link delay properties/states (i.e., delay distribution and delay average range). Nevertheless, it is difficult to acquire accurate link delay states to approximate the link characteristics due to possible measurement errors. In this paper, we first proposed a convenient DSSP estimation approach to approximate the link stochastic delay considering the tradeoff between the immediate delay and historical delay samples in stochastic overlay networks. Then, in order to evaluate the performance of DSSP, we conducted a comprehensive simulation study to compare DSSP with the shortest path computed using classic routing algorithms with the average delay values and delay errors due to the variation of delay distributions and updating intervals. The experiment results show that the proposed DSSP delay estimation method is more reliable and outperforms the conventional shortest path routing with the delay estimation using average delay and delay errors. In addition, we also proposed a refined heuristic K-shortest stochastic path routing algorithm using the proposed delay estimation method. In two typical overlay relay network scenarios, the simulation results show that the proposed stochastic routing algorithm outperforms the classic routing algorithms in reducing the average delay by 20% - 40% and the packet loss for nearly 50%.