P2PMM_router: A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks

Nobuo FUNABIKI; Jun KAWASHIMA; Shoji YOSHIDA; Kiyohiko OKAYAMA; Toru NAKANISHI; Teruo HIGASHINO

P2PMM_router: A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks

Nobuo FUNABIKI, Jun KAWASHIMA, Shoji YOSHIDA, Kiyohiko OKAYAMA, Toru NAKANISHI, Teruo HIGASHINO

Full Text Views

0

Share
Cite this

Summary :

A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1070-1076

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Nobuo FUNABIKI, Jun KAWASHIMA, Shoji YOSHIDA, Kiyohiko OKAYAMA, Toru NAKANISHI, Teruo HIGASHINO, "P2PMM_router: A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1070-1076, May 2004, doi: .
Abstract: A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1070/_p

Copy

@ARTICLE{e87-a_5_1070,
author={Nobuo FUNABIKI, Jun KAWASHIMA, Shoji YOSHIDA, Kiyohiko OKAYAMA, Toru NAKANISHI, Teruo HIGASHINO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={P2PMM_router: A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks},
year={2004},
volume={E87-A},
number={5},
pages={1070-1076},
abstract={A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - P2PMM_router: A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1070
EP - 1076
AU - Nobuo FUNABIKI
AU - Jun KAWASHIMA
AU - Shoji YOSHIDA
AU - Kiyohiko OKAYAMA
AU - Toru NAKANISHI
AU - Teruo HIGASHINO
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.
ER -