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
본 논문에서는 개별 스위칭 노드의 패킷(셀) 복제 기능에 제약이 있을 때 ATM 네트워크와 같은 패킷 교환 네트워크에서 멀티캐스트 트리를 얻는 방법에 대해 설명합니다. 이 문제는 노드의 차수 경계가 있는 슈타이너 트리 문제로 공식화될 수 있으므로 이를 호출합니다. 학위 제약 스타이너 트리 문제 (DCST). 네 가지 휴리스틱 알고리즘이 제안됩니다. 첫 번째는 잘 알려진 두 가지 스타이너 트리 알고리즘을 결합한 버전입니다. 소박한 그리고 최단 경로 휴리스틱 (SPH)이고 두 번째는 휴식 DCST의 수학적 공식을 기반으로 한 알고리즘이며 마지막 두 개는 트리 재구성 '라는 개념을 기반으로 한 계획논리적 링크. ' 우리는 세 가지 측면에서 우리의 알고리즘을 이전 알고리즘과 실험적으로 비교합니다. 해결된 인스턴스 수, 객관적인 가치 또는 나무 비용및 계산 시간. 실험 결과에 따르면 우리 알고리즘에 의해 해결되지 않은 사례가 거의 없으며 객관적인 값은 대부분 최적의 5% 이내에 있습니다. 계산 시간도 허용됩니다.
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.
부
Sung-Jin CHUNG, Sung-Pil HONG, Hoo-Sang CHUNG, "Efficient Algorithms for the Multicast Trees under the Packet-Replication Restrictions" in IEICE TRANSACTIONS on Communications,
vol. E84-B, no. 9, pp. 2670-2680, September 2001, doi: .
Abstract: In this paper, we are concerned in obtaining multicast trees in packet-switched networks such as ATM nets, when there exist constraints on the packet (cell)-replication capabilities of the individual switching nodes. This problem can be formulated as the Steiner tree problem with degree bounds on the nodes, so we call it the Degree-Constrained Steiner Tree problem (DCST). Four heuristic algorithms are proposed: the first is a combined version of two well-known Steiner tree algorithms, heuristic Naive and the shortest path heuristic (SPH), and the second is a relaxation algorithm based on a mathematical formulation of the DCST, and the last two use a tree reconfiguration scheme based on the concept of 'logical link. ' We experimentally compare our algorithms with the previous ones in three respects; number of solved instances, objective value or tree cost, and computation time. The experimental results show that there are few instances unsolved by our algorithms, and the objective values are mostly within 5% of optimal. Computation times are also acceptable.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e84-b_9_2670/_p
부
@ARTICLE{e84-b_9_2670,
author={Sung-Jin CHUNG, Sung-Pil HONG, Hoo-Sang CHUNG, },
journal={IEICE TRANSACTIONS on Communications},
title={Efficient Algorithms for the Multicast Trees under the Packet-Replication Restrictions},
year={2001},
volume={E84-B},
number={9},
pages={2670-2680},
abstract={In this paper, we are concerned in obtaining multicast trees in packet-switched networks such as ATM nets, when there exist constraints on the packet (cell)-replication capabilities of the individual switching nodes. This problem can be formulated as the Steiner tree problem with degree bounds on the nodes, so we call it the Degree-Constrained Steiner Tree problem (DCST). Four heuristic algorithms are proposed: the first is a combined version of two well-known Steiner tree algorithms, heuristic Naive and the shortest path heuristic (SPH), and the second is a relaxation algorithm based on a mathematical formulation of the DCST, and the last two use a tree reconfiguration scheme based on the concept of 'logical link. ' We experimentally compare our algorithms with the previous ones in three respects; number of solved instances, objective value or tree cost, and computation time. The experimental results show that there are few instances unsolved by our algorithms, and the objective values are mostly within 5% of optimal. Computation times are also acceptable.},
keywords={},
doi={},
ISSN={},
month={September},}
부
TY - JOUR
TI - Efficient Algorithms for the Multicast Trees under the Packet-Replication Restrictions
T2 - IEICE TRANSACTIONS on Communications
SP - 2670
EP - 2680
AU - Sung-Jin CHUNG
AU - Sung-Pil HONG
AU - Hoo-Sang CHUNG
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E84-B
IS - 9
JA - IEICE TRANSACTIONS on Communications
Y1 - September 2001
AB - In this paper, we are concerned in obtaining multicast trees in packet-switched networks such as ATM nets, when there exist constraints on the packet (cell)-replication capabilities of the individual switching nodes. This problem can be formulated as the Steiner tree problem with degree bounds on the nodes, so we call it the Degree-Constrained Steiner Tree problem (DCST). Four heuristic algorithms are proposed: the first is a combined version of two well-known Steiner tree algorithms, heuristic Naive and the shortest path heuristic (SPH), and the second is a relaxation algorithm based on a mathematical formulation of the DCST, and the last two use a tree reconfiguration scheme based on the concept of 'logical link. ' We experimentally compare our algorithms with the previous ones in three respects; number of solved instances, objective value or tree cost, and computation time. The experimental results show that there are few instances unsolved by our algorithms, and the objective values are mostly within 5% of optimal. Computation times are also acceptable.
ER -