| Item type |
SIG Technical Reports(1) |
| 公開日 |
2014-12-02 |
| タイトル |
|
|
タイトル |
A New Parametric Method for Localized Star Spanning Tree Generation |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A New Parametric Method for Localized Star Spanning Tree Generation |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
University of Electro-Communications |
| 著者所属 |
|
|
|
University of Electro-Communications |
| 著者所属 |
|
|
|
University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
University of Electro-Communications |
| 著者名 |
Kazuaki, Oya
Toshinori, Watanabe
Hisashi, Koga
|
| 著者名(英) |
Kazuaki, Oya
Toshinori, Watanabe
Hisashi, Koga
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
A typical network topological design problem is to determine link connections and their capacity to achieve high performance, low initial and operational costs, and high reliability under the given traffic and link length data between nodes. Because of the difficulties of this problem, approximate solutions such as probabilistic searches have long been studied. However, the real-world network topologies seem to be more type oriented than the above traditional computer based solutions. In fact, most real network topologies consist of a hierarchical combination of basic types such as the bus, the star, and the ring to avoid the difficulties of the design problem. In this paper, a new parametric method for localized spanning tree (ST) generation is proposed with good experimental results. The method performs node clustering and physical link generation in one step. This is realized by a new idea of the parameterized virtual node distance incorporating both the physical node distance and the traffic gravity between nodes with a parametric weight. A set of localized spanning trees can be generated on traditional MST algorithm, by changing the weight. As the main computational costs are the MST generation and the depth-first shortest-route search, which is not very expensive, so this is a high-speed approximate solver of the network topology design problem. To assist selecting a good solution, a link capacity determination function to achieve the given mean delay time and the monthly cost estimation function are incorporated. Approximate mathematical discussions to prove the existence of a minimum cost solution in the generated candidates is given also. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
A typical network topological design problem is to determine link connections and their capacity to achieve high performance, low initial and operational costs, and high reliability under the given traffic and link length data between nodes. Because of the difficulties of this problem, approximate solutions such as probabilistic searches have long been studied. However, the real-world network topologies seem to be more type oriented than the above traditional computer based solutions. In fact, most real network topologies consist of a hierarchical combination of basic types such as the bus, the star, and the ring to avoid the difficulties of the design problem. In this paper, a new parametric method for localized spanning tree (ST) generation is proposed with good experimental results. The method performs node clustering and physical link generation in one step. This is realized by a new idea of the parameterized virtual node distance incorporating both the physical node distance and the traffic gravity between nodes with a parametric weight. A set of localized spanning trees can be generated on traditional MST algorithm, by changing the weight. As the main computational costs are the MST generation and the depth-first shortest-route search, which is not very expensive, so this is a high-speed approximate solver of the network topology design problem. To assist selecting a good solution, a link capacity determination function to achieve the given mean delay time and the monthly cost estimation function are incorporated. Approximate mathematical discussions to prove the existence of a minimum cost solution in the generated candidates is given also. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10505667 |
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS）
巻 2014-MPS-101,
号 2,
p. 1-5,
発行日 2014-12-02
|
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-MPS14101002.pdf (1.3 MB)
