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
Masalah mencari pokok multicast minimum-cast (pokok Steiner) dikenali sebagai NP complete. Algoritma berasaskan heuristik untuk masalah ini untuk mencapai prestasi yang baik biasanya memakan masa. Dalam makalah ini, kami mencadangkan strategi baharu yang dipanggil penyimpan pokok untuk persediaan sambungan multicast yang cekap dalam rangkaian berorientasikan sambungan. Dalam skema ini, topologi pokok yang telah dikira dicache dalam pangkalan data nod sumber. Ini boleh mengurangkan masa penubuhan sambungan untuk permintaan sambungan berikutnya yang mempunyai beberapa ahli multicast biasa, dengan penggunaan semula pepohon cache yang cekap tanpa perlu menjalankan semula algoritma penghalaan multicast untuk keseluruhan kumpulan. Kaedah ini boleh menyediakan cara yang cekap untuk menghapuskan, apabila mungkin, algoritma pengiraan pokok mahal yang perlu dilakukan dalam menyediakan sambungan multicast. Kami mula-mula merumuskan masalah cache pokok dan kemudian mencadangkan algoritma cache pokok untuk mengurangkan kerumitan pengiraan pokok apabila sambungan baharu akan diwujudkan. Melalui simulasi, kami mendapati bahawa strategi caching pokok yang dicadangkan berfungsi dengan baik dan boleh mengurangkan kerumitan pengiraan dengan ketara untuk menyediakan sambungan multicast.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -