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
최소 캐스트 멀티캐스트 트리(스타이너 트리)를 찾는 문제를 NP 완료라고 합니다. 좋은 성능을 달성하기 위한 이 문제에 대한 경험적 기반 알고리즘은 일반적으로 시간이 많이 걸립니다. 본 논문에서는 연결 지향 네트워크에서 효율적인 멀티캐스트 연결 설정을 위한 트리 캐싱이라는 새로운 전략을 제안합니다. 이 체계에서는 계산된 트리 토폴로지가 소스 노드의 데이터베이스에 캐시됩니다. 이는 전체 그룹에 대해 멀티캐스트 라우팅 알고리즘을 다시 실행할 필요 없이 캐시된 트리를 효율적으로 재사용하여 일부 공통 멀티캐스트 구성원이 있는 후속 연결 요청에 대한 연결 설정 시간을 줄일 수 있습니다. 이 방법은 멀티캐스트 연결을 설정할 때 수행해야 하는 값비싼 트리 계산 알고리즘을 가능한 한 제거하는 효율적인 방법을 제공할 수 있습니다. 우리는 먼저 트리 캐싱 문제를 공식화한 다음 새로운 연결이 설정될 때 트리 계산의 복잡성을 줄이기 위한 트리 캐싱 알고리즘을 제안합니다. 시뮬레이션을 통해 우리는 제안된 트리 캐싱 전략이 매우 잘 수행되고 멀티캐스트 연결 설정을 위한 계산 복잡성을 크게 줄일 수 있음을 확인했습니다.
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.
부
David Chee Kheong SIEW, Gang FENG, "Tree-Caching for Multicast Connections with End-to-End Delay Constraint" in IEICE TRANSACTIONS on Communications,
vol. E84-B, no. 4, pp. 1030-1040, April 2001, doi: .
Abstract: The problem of finding a minimum-cast multicast tree (Steiner tree) is known as NP complete. Heuristic based algorithms for this problem to achieve good performance are usually time-consuming. In this paper, we propose a new strategy called tree-caching for efficient multicast connection setup in connection-oriented networks. In this scheme, the tree topologies that have been computed are cached in a database of the source nodes. This can reduce the connection establishment time for subsequent connection requests which have some common multicast members, by an efficient reuse of cached trees without having to re-run a multicast routing algorithm for the whole group. This method can provide an efficient way to eliminate, when ever possible, the expensive tree computation algorithm that has to be performed in setting up a multicast connection. We first formulate the problem of tree-caching and then propose a tree-caching algorithm to reduce the complexity of the tree computations when a new connection is to be established. Through simulations, we find that the proposed tree-caching strategy performs very well and can significantly reduce the computation complexity for setting up multicast connections.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e84-b_4_1030/_p
부
@ARTICLE{e84-b_4_1030,
author={David Chee Kheong SIEW, Gang FENG, },
journal={IEICE TRANSACTIONS on Communications},
title={Tree-Caching for Multicast Connections with End-to-End Delay Constraint},
year={2001},
volume={E84-B},
number={4},
pages={1030-1040},
abstract={The problem of finding a minimum-cast multicast tree (Steiner tree) is known as NP complete. Heuristic based algorithms for this problem to achieve good performance are usually time-consuming. In this paper, we propose a new strategy called tree-caching for efficient multicast connection setup in connection-oriented networks. In this scheme, the tree topologies that have been computed are cached in a database of the source nodes. This can reduce the connection establishment time for subsequent connection requests which have some common multicast members, by an efficient reuse of cached trees without having to re-run a multicast routing algorithm for the whole group. This method can provide an efficient way to eliminate, when ever possible, the expensive tree computation algorithm that has to be performed in setting up a multicast connection. We first formulate the problem of tree-caching and then propose a tree-caching algorithm to reduce the complexity of the tree computations when a new connection is to be established. Through simulations, we find that the proposed tree-caching strategy performs very well and can significantly reduce the computation complexity for setting up multicast connections.},
keywords={},
doi={},
ISSN={},
month={April},}
부
TY - JOUR
TI - Tree-Caching for Multicast Connections with End-to-End Delay Constraint
T2 - IEICE TRANSACTIONS on Communications
SP - 1030
EP - 1040
AU - David Chee Kheong SIEW
AU - Gang FENG
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E84-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 2001
AB - The problem of finding a minimum-cast multicast tree (Steiner tree) is known as NP complete. Heuristic based algorithms for this problem to achieve good performance are usually time-consuming. In this paper, we propose a new strategy called tree-caching for efficient multicast connection setup in connection-oriented networks. In this scheme, the tree topologies that have been computed are cached in a database of the source nodes. This can reduce the connection establishment time for subsequent connection requests which have some common multicast members, by an efficient reuse of cached trees without having to re-run a multicast routing algorithm for the whole group. This method can provide an efficient way to eliminate, when ever possible, the expensive tree computation algorithm that has to be performed in setting up a multicast connection. We first formulate the problem of tree-caching and then propose a tree-caching algorithm to reduce the complexity of the tree computations when a new connection is to be established. Through simulations, we find that the proposed tree-caching strategy performs very well and can significantly reduce the computation complexity for setting up multicast connections.
ER -