Multi-path traffic engineering distributed VPLS routing algorithm

The paper proposes a multi-path routing algorithm to guarantee the bandwidth QoS requirements of point to multipoint (P2MP) Virtual Private LAN Services (VPLS). The probability to find a single feasible path which satisfies a VPLS bandwidth requirement is low for connection requests with large bandwidth constraint requirements or when the network is congested. Thus, the proposed algorithm divides the required constraint into sub-constraints and finds the minimum number of optimum P2MP paths that meet the sub-constraint requirement. Most of the work in the area of multi-path routing is focused on partitioning the traffic among multiple point to point (P2P) paths. The traffic is partitioned to reduce the network congestion or to adaptively balance the load among multiple paths based on the network status. The novelty of the proposed algorithm is that the algorithm finds the minimum number of paths that satisfy certain bandwidth QoS constraint. Additionally, the multi-path route is calculated to avoid the critical links of other ingress routers and balances the load by choosing paths with maximum residual bandwidth. The proposed algorithm performance is validated using extensive simulation. The results show that the algorithm is capable of increasing the number of admitted requests and improve the network resource utilization by avoiding critical links and choosing paths with maximum residual bandwidth.