Maximizing Bandwidth Using Disjoint Paths

Recently, multi-paths solutions have been proposed to improve the quality-of-service (QoS) in communication networks (CNs). This paper addresses the problem to obtain the λ-edge-disjoint-path-set (λ DP/B) with maximum bandwidth (λ DP^B), for λ≥1. λDP/B is useful for applications that require maximum bandwidth for data transmission, such as video conferencing, video-on-demand, large file downloads and FTP. We propose a polynomial time heuristic algorithm, Maximum Bandwidth Algorithm (MBA), to solve the problem. We have implemented MBA and evaluated its performance against an optimal, but exponential time, brute force algorithm (BF) and three existing heuristic algorithms: Algorithm-1, CBA-G´, DPSP´. Simulations on seventy CNs show that MBA is able to produce the optimal λ DP^B for about 99% of the time while using only 0.005% CPU time of BF. Our simulations also show that MBA is significantly more effective than these existing algorithms while using competitive CPU time.