期刊名称：International Journal of Advanced Networking and Applications
电子版ISSN：0975-0290
出版年度：2012
卷号：3
期号：4
页码：1292-1297
出版社：Eswar Publications
摘要：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
关键词：Congestion Avoidance; Multi path routing; NP-hard; Quality of Service; Routing protocols
