کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
453265 | 694769 | 2007 | 13 صفحه PDF | دانلود رایگان |
Disjoint multipath routing (DMPR) is an effective strategy to achieve robustness in networks where data is forwarded along multiple link- or node-disjoint paths. DMPR poses significant challenges in terms of obtaining loop-free multiple (disjoint) paths and effectively forwarding data over the multiple paths, the latter being particularly significant in datagram networks. One approach to reduce the number of routing table entries for disjoint multipath forwarding is to construct two trees, namely red and blue, rooted at a destination node such that the paths from a source to the destination on the two trees are link/node-disjoint. This paper develops the first distributed algorithm for constructing the colored trees whose running time is linear in the number of links in the network. The paper also demonstrates the effectiveness of employing generalized low-point concept rather than traditional low-point concept in the DFS-tree to reduce the average path lengths on the colored trees.
Journal: Computer Networks - Volume 51, Issue 10, 11 July 2007, Pages 2854–2866