k-Maximally Disjoint Path Routing Algorithms for SDN

Abstract

The problem of path optimization and k disjoint pairs are important in survivable, QoS-aware communication network and SDN controlled networks. While the problem of optimally solving for maximally link-disjoint path pairs have always received a good level of attention, more work is needed with respect to k-maximally disjoint, multi-constrained, multiple QoS link weights route provisioning, and efficient hybrid algorithms for the problem. We propose a model algorithm to find k-maximally link-disjoint paths with Cost (kMDPC) for QoS routing with respect to source and destination pairs that ensures reliability, flexibility, and survivability. The computational complexity of our algorithm is efficient with the use of a modified Dijkstra's algorithm. The maximum k numbers of paths are maximally disjoint paths for survivability, robustness and also at the long run to satisfy a multiple set of defined QoS weight value constraints. The multiple QoS constraints addressed by the heuristic algorithm are of the delay, delay-jitter, bandwidth, link length and link cost parameter. In polynomial time, kMDPC finds very high number of average maximally disjoint paths. The path diversity through the paths disjointness capabilities for the SDN data-plane, provided by kMDPC will also help in the switch load-balancing, Controller load-balancing and multiple flow tables management by the SDN since the provisioned paths are with the required QoS.