期刊
IEEE-ACM TRANSACTIONS ON NETWORKING
卷 12, 期 5, 页码 851-864出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2004.836112
关键词
look-ahead; path dominance; QoS routing; shortest path
The underlying concepts of an exact QoS routing algorithm are explained. We show that these four concepts, namely 1) nonlinear definition of the path length; 2) a k-shortest path approach; 3) nondominance; and 4) look-ahead, are fundamental building blocks of a multiconstrained routing algorithm. The main reasons to consider exact multiconstrained routing algorithms are as follows. First, the NP-complete behavior seems only to occur in specially constructed graphs, which are unlikely to occur in realistic communication networks. Second, there exist exact algorithms that are equally complex as heuristics in algorithmic structure and in running time on topologies that do not induce NP-complete behavior. Third, by simply restricting the number k of paths explored during the path computation, the computational complexity can be decreased at the expense of possibly loosing exactness. The presented four concepts are incorporated in SAMCRA, a self-adaptive multiple constraints routing algorithm.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据