Maximizing bandwidth using disjoint paths

Abstract

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 (λDPB), 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 heuristicalgorithms: Algorithm-1, CBA-G', DPSP'. Simulations on seventy CNs show that MBA is able to produce the optimal λDPB for about 99% of the time while using only 0.005% CPU time of BF. Our simulations also show that MBA issignificantly more effective than these existing algorithms while using competitive CPU time.