Reliable Shortest Path Routing with Applications to Wireless Software-Defined Networking
Weijia Wang, Chang‐Heng Wang, Tara Javidi · 2018
This paper considers centralized routing over a network in which the cost of each edge is modeled as a random variable and the objective is to route the packets in a manner that minimizes the expected cost while constraining the variance of the cost to a pre- determined upper bound. This problem arises in the context of flow-based routing for wireless Software-Defined Networks (SDN). A Randomized Dijkstra-based Algorithm (RDBR) with a Lagrangian Relaxation Cost is proposed in which two distinct shortest paths are utilized randomly with an optimized randomization factor. Here the notion of shortest path identified by Dijkstra's algorithm refers to the property that these two paths both are of minimum regularized cost as defined by the expected total cost plus weighted variance. We prove the existence and optimality when the weight coincides with the optimal Lagrange multiplier and propose a sub-gradient descent method to compute the optimal multiplier. Numerical comparisons against other previously proposed solutions in the literature illustrate the performance improvements under RDBR at a significantly lower or comparable computational complexity.