Algebra and algorithms for efficient and correct multipath QoS routing in link state networks
Algebra and algorithms for efficient and correct multipath QoS routing in link state networks
复制标题
DOI：
10.1109/iwqos.2015.7404744
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Haijun Geng;Xingang Shi;Xia Yin;Zhiliang Wang;Han Zhang
中科院分区：
文献类型：
--
作者：
Haijun Geng;Xingang Shi;Xia Yin;Zhiliang Wang;Han Zhang
Internet应用对QoS（Quality-of-Service）要求的多样性促使各种QoS路由算法考虑不同的QoS度量。路由代数已经被提出作为一个框架来研究QoS路由算法的基本属性，如它们的最优性和无环性。然而，对于多路径QoS路由，很少有做在这些方面。现有的多径QoS路由算法往往采取一个相当保守的方法来保证无环，在效率的成本。另一方面，简单地调整现有的有效的多路径路由算法，以支持各种QoS指标不能保证正确性。针对这一问题，本文提出了一种链路状态网络中多径QoS路由的路由度量代数，其中路由度量的一个重要性质叫做保序性，它在路由度量中起着重要的作用。为了让路由器有效地和正确地找到多个下一跳为每个目的地，我们还开发了两个分布式多路径QoS路由算法。这些算法在本地独立运行，除了基本链路状态之外不交换其他消息。它们是专门为具有严格或非严格保序性的代数量身定制的，并给出了它们的正确性的形式证明。
The diversity of QoS (Quality-of-Service) requirements of Internet applications motivates various QoS routing algorithms that take different QoS metrics into consideration. Routing algebra has been proposed as a framework to study the fundamental properties of QoS routing algorithms, such as their optimality and loop-freeness. However, for multipath QoS routing, little has been done in these aspects. Existing multipath QoS routing algorithms often take a rather conservative approach to guarantee loop-freeness, at the cost of efficiency. On the other hand, simply adapting existing efficient multipath routing algorithms to support various QoS metrics cannot guarantee correctness. In face of that, we propose a routing metric algebra for multipath QoS routing in link state networks, where a key property of the routing metrics called isotonicity, which plays an important role. To let routers efficiently and correctly find multiple next-hops for each destination, we also develop two distributed multipath QoS routing algorithms. The algorithms are run locally and independently, without exchanging messages other than the basic link states. They are specifically tailored for algebras with strict or non strict isotonicity, and their correctness are formally proved.