Premium
Rate‐adaptive multipath routing: Distributed, centralized, and hybrid architectures
Author(s) -
Németh Gábor,
Rétvári Gábor
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21617
Subject(s) - computer science , hybrid routing , multipath routing , distributed computing , routing (electronic design automation) , static routing , destination sequenced distance vector routing , policy based routing , computer network , link state routing protocol , routing protocol
With the increasing volume and volatility of Internet traffic, the need for adaptive routing algorithms has become compelling lately. An adaptive routing algorithm controls the rate at which traffic is placed on forwarding paths in concert with the actual user demands, making it possible to avoid congestion even when no information on expected traffic is available. In this article, we present a new model for rate‐adaptive multipath routing, which allows one to analyze distributed, centralized, and hybrid routing architectures within a single framework, and to develop quantitative as well as qualitative arguments regarding their optimality, stability, and realizability. By a novel generalization of oblivious routing, we present a centralized algorithm with provable optimality, and we arrive at the conclusion that congestion can be completely eliminated even if routing decisions are completely precomputed. We find, although, that the complexity of the centralized scheme can become exponential. Therefore, we develop a hybrid distributed‐centralized algorithm that combines the simplicity of distributed algorithms with the efficiency of centralized ones, and we provide numerical studies demonstrating that the hybrid scheme performs well in a broad selection of realistic scenarios. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 118–135 2015