Efficient Algorithms for the Multicast Trees under the Packet-Replication Restrictions

Sung-Jin CHUNG; Sung-Pil HONG; Hoo-Sang CHUNG

Efficient Algorithms for the Multicast Trees under the Packet-Replication Restrictions

Sung-Jin CHUNG, Sung-Pil HONG, Hoo-Sang CHUNG

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Communications Vol.E84-B No.9 pp.2670-2680

Publication Date: 2001/09/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Network

Cite this

Copy

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

Copy

@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},}

Copy

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 -