Cached Shortest-Path Tree: An Approach to Reduce the Influence of Intra-Domain Routing Instability

Shu ZHANG; Katsuyoshi IIDA; Suguru YAMAGUCHI

Cached Shortest-Path Tree: An Approach to Reduce the Influence of Intra-Domain Routing Instability

Shu ZHANG, Katsuyoshi IIDA, Suguru YAMAGUCHI

Full Text Views

0

Cite this

Summary :

Because most link-state routing protocols, such as OSPF and IS-IS, calculate routes using the Dijkstra algorithm, which poses scalability problems, implementors often introduce an artificial delay to reduce the number of route calculations. Although this delay directly affects IP packet forwarding, it can be acceptable when the network topology does not change often. However, when the topology of a network changes frequently, this delay can lead to a complete loss of IP reachability for the affected network prefixes during the unstable period. In this paper, we propose the Cached Shortest-path Tree (CST) approach, which speeds up intra-domain routing convergence without extra execution of the Dijkstra algorithm, even if the routing for a network is quite unstable. The basic idea of CST is to cache shortest-path trees (SPTs) of network topologies that appear frequently, and use these SPTs to instantly generate a routing table when the topology after a change matches one in the caches. CST depends on a characteristic that we found from an investigation of routing instability conducted on the WIDE Internet in Japan. That is, under unstable routing conditions, both frequently changing Link State Advertisements (LSAs) and their instances tend to be limited. At the end of this paper, we show CST's effectiveness by a trace-driven simulation.

Publication: IEICE TRANSACTIONS on Communications Vol.E86-B No.12 pp.3590-3599

Publication Date: 2003/12/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Network

Cite this

Copy

Shu ZHANG, Katsuyoshi IIDA, Suguru YAMAGUCHI, "Cached Shortest-Path Tree: An Approach to Reduce the Influence of Intra-Domain Routing Instability" in IEICE TRANSACTIONS on Communications, vol. E86-B, no. 12, pp. 3590-3599, December 2003, doi: .
Abstract: Because most link-state routing protocols, such as OSPF and IS-IS, calculate routes using the Dijkstra algorithm, which poses scalability problems, implementors often introduce an artificial delay to reduce the number of route calculations. Although this delay directly affects IP packet forwarding, it can be acceptable when the network topology does not change often. However, when the topology of a network changes frequently, this delay can lead to a complete loss of IP reachability for the affected network prefixes during the unstable period. In this paper, we propose the Cached Shortest-path Tree (CST) approach, which speeds up intra-domain routing convergence without extra execution of the Dijkstra algorithm, even if the routing for a network is quite unstable. The basic idea of CST is to cache shortest-path trees (SPTs) of network topologies that appear frequently, and use these SPTs to instantly generate a routing table when the topology after a change matches one in the caches. CST depends on a characteristic that we found from an investigation of routing instability conducted on the WIDE Internet in Japan. That is, under unstable routing conditions, both frequently changing Link State Advertisements (LSAs) and their instances tend to be limited. At the end of this paper, we show CST's effectiveness by a trace-driven simulation.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e86-b_12_3590/_p

Copy

@ARTICLE{e86-b_12_3590,
author={Shu ZHANG, Katsuyoshi IIDA, Suguru YAMAGUCHI, },
journal={IEICE TRANSACTIONS on Communications},
title={Cached Shortest-Path Tree: An Approach to Reduce the Influence of Intra-Domain Routing Instability},
year={2003},
volume={E86-B},
number={12},
pages={3590-3599},
abstract={Because most link-state routing protocols, such as OSPF and IS-IS, calculate routes using the Dijkstra algorithm, which poses scalability problems, implementors often introduce an artificial delay to reduce the number of route calculations. Although this delay directly affects IP packet forwarding, it can be acceptable when the network topology does not change often. However, when the topology of a network changes frequently, this delay can lead to a complete loss of IP reachability for the affected network prefixes during the unstable period. In this paper, we propose the Cached Shortest-path Tree (CST) approach, which speeds up intra-domain routing convergence without extra execution of the Dijkstra algorithm, even if the routing for a network is quite unstable. The basic idea of CST is to cache shortest-path trees (SPTs) of network topologies that appear frequently, and use these SPTs to instantly generate a routing table when the topology after a change matches one in the caches. CST depends on a characteristic that we found from an investigation of routing instability conducted on the WIDE Internet in Japan. That is, under unstable routing conditions, both frequently changing Link State Advertisements (LSAs) and their instances tend to be limited. At the end of this paper, we show CST's effectiveness by a trace-driven simulation.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Cached Shortest-Path Tree: An Approach to Reduce the Influence of Intra-Domain Routing Instability
T2 - IEICE TRANSACTIONS on Communications
SP - 3590
EP - 3599
AU - Shu ZHANG
AU - Katsuyoshi IIDA
AU - Suguru YAMAGUCHI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E86-B
IS - 12
JA - IEICE TRANSACTIONS on Communications
Y1 - December 2003
AB - Because most link-state routing protocols, such as OSPF and IS-IS, calculate routes using the Dijkstra algorithm, which poses scalability problems, implementors often introduce an artificial delay to reduce the number of route calculations. Although this delay directly affects IP packet forwarding, it can be acceptable when the network topology does not change often. However, when the topology of a network changes frequently, this delay can lead to a complete loss of IP reachability for the affected network prefixes during the unstable period. In this paper, we propose the Cached Shortest-path Tree (CST) approach, which speeds up intra-domain routing convergence without extra execution of the Dijkstra algorithm, even if the routing for a network is quite unstable. The basic idea of CST is to cache shortest-path trees (SPTs) of network topologies that appear frequently, and use these SPTs to instantly generate a routing table when the topology after a change matches one in the caches. CST depends on a characteristic that we found from an investigation of routing instability conducted on the WIDE Internet in Japan. That is, under unstable routing conditions, both frequently changing Link State Advertisements (LSAs) and their instances tend to be limited. At the end of this paper, we show CST's effectiveness by a trace-driven simulation.
ER -