| Presentation | 2004/1/23 A perfect k-ary peer-to-peer multicast routing tree search algorithm for multihome networks Jun KAWASHIMA, Nobuo FUNABIKI, Kiyohiko OKAYAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we present a two-stage heuristic algorithm for the peer-to-peer multicast routing problem in a multihome network. This problem requires finding a multicast routing tree satisfying the delay constraint between any two hosts and the degree constraint of any host while minimizing the total cost of the tree. In our algorithm, the routing tree topology is fixed to the perfect k-ary tree so as to always satisfy the degree constraint while minimizing the maximum hop count between hosts. The first stage of the algorithm greedily constructs an initial tree of minimizing the cost, and the second stage iteratively searches a feasible tree based on the annealing method. Through simulations using random network instances, we compare the performance of our algorithm to that of a similar existing algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | peer-to-peer multicast / real-time communication / multihome network / heuristic algorithm / perfect k-ary tree / NP-hard |
| Paper # | OCS2003-126 |
| Date of Issue |
| Conference Information | |
| Committee | OCS |
|---|---|
| Conference Date | 2004/1/23(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Optical Communication Systems (OCS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A perfect k-ary peer-to-peer multicast routing tree search algorithm for multihome networks |
| Sub Title (in English) | |
| Keyword(1) | peer-to-peer multicast |
| Keyword(2) | real-time communication |
| Keyword(3) | multihome network |
| Keyword(4) | heuristic algorithm |
| Keyword(5) | perfect k-ary tree |
| Keyword(6) | NP-hard |
| 1st Author's Name | Jun KAWASHIMA |
| 1st Author's Affiliation | Dept. of Communication Network Engineering, Okayama University() |
| 2nd Author's Name | Nobuo FUNABIKI |
| 2nd Author's Affiliation | Dept. of Communication Network Engineering, Okayama University |
| 3rd Author's Name | Kiyohiko OKAYAMA |
| 3rd Author's Affiliation | Dept. of Communication Network Engineering, Okayama University |
| Date | 2004/1/23 |
| Paper # | OCS2003-126 |
| Volume (vol) | vol.103 |
| Number (no) | 627 |
| Page | pp.pp.- |
| #Pages | 4 |
| Date of Issue | |