Open Access Open Access  Restricted Access Subscription Access

Multipath Routing Algorithms for Congestion Minimization


Affiliations
1 Department of Computer Science and Engineering, CSI College of Engineering, Ketti-643215, The Nilgiris, India
2 Department of Mathematics, CSI College of Engineering, Ketti-643215, The Nilgiris, India
 

Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the single-path routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing. Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish efficient solutions with proven performance guarantees.

Keywords

Congestion Avoidance, Multi Path Routing, NP-Hard, Quality of Service, Routing Protocols.
User
Notifications
Font Size

Abstract Views: 483

PDF Views: 0




  • Multipath Routing Algorithms for Congestion Minimization

Abstract Views: 483  |  PDF Views: 0

Authors

B. Sasthiri
Department of Computer Science and Engineering, CSI College of Engineering, Ketti-643215, The Nilgiris, India
T. Prakash
Department of Mathematics, CSI College of Engineering, Ketti-643215, The Nilgiris, India

Abstract


Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the single-path routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing. Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish efficient solutions with proven performance guarantees.

Keywords


Congestion Avoidance, Multi Path Routing, NP-Hard, Quality of Service, Routing Protocols.