The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
조회수
95
최근에는 최신 포워딩 메커니즘인 세그먼트 라우팅(Segment Routing)과 세그먼트 라우팅을 이용한 IP Fast-Reroute 방식인 Topology Independent Loop-free Alternate가 제안되어 실제 네트워크에 적용되기 시작했습니다. 네트워크에 오류가 발생하면 TI-LFA는 다른 노드가 라우팅 테이블을 업데이트할 때까지 기다리지 않고 패킷 전달을 신속하게 복원합니다. 재라우팅 경로에 루프가 발생할 수 있는 섹션을 전달하기 위해 세그먼트 라우팅을 사용하여 이를 수행합니다. 그러나 세그먼트 라우팅 구간을 결정하는 것은 각 목적지에 대한 계산이 필요하기 때문에 계산 비용이 높습니다. 따라서 본 논문에서는 2.0개의 최단 경로 트리 계산만으로 모든 목적지 노드에 대해 세그먼트 라우팅 구간의 출구인 출구 노드를 결정하는 알고리즘을 제안한다. 제안한 알고리즘의 평가 결과, 네트워크 규모에 관계없이 평균 터널 길이는 최대 2.2~XNUMX홉인 것으로 나타났다. 또한 제안된 알고리즘의 계산 복잡도가 다음과 같다는 것을 보여주었습니다. O(N기록 N).
Kazuya SUZUKI
Akita Prefectural University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Kazuya SUZUKI, "An Efficient Calculation for TI-LFA Rerouting Path" in IEICE TRANSACTIONS on Communications,
vol. E105-B, no. 2, pp. 196-204, February 2022, doi: 10.1587/transcom.2021CEP0003.
Abstract: Recently, segment routing, which is a modern forwarding mechanism, and Topology Independent Loop-free Alternate, which is an IP fast-reroute method using segment routing, have been proposed and have begun to be applied to real networks. When a failure occurs in a network, TI-LFA quickly restores packet forwarding without waiting for other nodes to update their routing tables. It does so by using segment routing to forward sections that may cause loops in the rerouting path. However, determining the segment routing sections has a high computational cost because it requires computation for each destination. This paper therefore proposes an algorithm to determine the egress node that is the exit of the segment routing section for all destination nodes with only three shortest-path tree calculations. The evaluation results of the proposed algorithm showed that the average tunnel lengths are at most 2.0 to 2.2 hops regardless of the size of the network. I also showed that the computational complexity of the proposed algorithm is O(Nlog N).
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2021CEP0003/_p
부
@ARTICLE{e105-b_2_196,
author={Kazuya SUZUKI, },
journal={IEICE TRANSACTIONS on Communications},
title={An Efficient Calculation for TI-LFA Rerouting Path},
year={2022},
volume={E105-B},
number={2},
pages={196-204},
abstract={Recently, segment routing, which is a modern forwarding mechanism, and Topology Independent Loop-free Alternate, which is an IP fast-reroute method using segment routing, have been proposed and have begun to be applied to real networks. When a failure occurs in a network, TI-LFA quickly restores packet forwarding without waiting for other nodes to update their routing tables. It does so by using segment routing to forward sections that may cause loops in the rerouting path. However, determining the segment routing sections has a high computational cost because it requires computation for each destination. This paper therefore proposes an algorithm to determine the egress node that is the exit of the segment routing section for all destination nodes with only three shortest-path tree calculations. The evaluation results of the proposed algorithm showed that the average tunnel lengths are at most 2.0 to 2.2 hops regardless of the size of the network. I also showed that the computational complexity of the proposed algorithm is O(Nlog N).},
keywords={},
doi={10.1587/transcom.2021CEP0003},
ISSN={1745-1345},
month={February},}
부
TY - JOUR
TI - An Efficient Calculation for TI-LFA Rerouting Path
T2 - IEICE TRANSACTIONS on Communications
SP - 196
EP - 204
AU - Kazuya SUZUKI
PY - 2022
DO - 10.1587/transcom.2021CEP0003
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E105-B
IS - 2
JA - IEICE TRANSACTIONS on Communications
Y1 - February 2022
AB - Recently, segment routing, which is a modern forwarding mechanism, and Topology Independent Loop-free Alternate, which is an IP fast-reroute method using segment routing, have been proposed and have begun to be applied to real networks. When a failure occurs in a network, TI-LFA quickly restores packet forwarding without waiting for other nodes to update their routing tables. It does so by using segment routing to forward sections that may cause loops in the rerouting path. However, determining the segment routing sections has a high computational cost because it requires computation for each destination. This paper therefore proposes an algorithm to determine the egress node that is the exit of the segment routing section for all destination nodes with only three shortest-path tree calculations. The evaluation results of the proposed algorithm showed that the average tunnel lengths are at most 2.0 to 2.2 hops regardless of the size of the network. I also showed that the computational complexity of the proposed algorithm is O(Nlog N).
ER -