| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-03-05 09:50 故障時性能劣化が小さいリンク数最小ネットワーク設計法 ○片山 希・藤村武史・巳波弘佳（関西学院大）・上山憲昭・長谷川治久・吉野秀明（NTT）  NS2009-228 |
|
| 抄録 | （和） | インターネットをはじめ，通信ネットワークが社会において必要不可欠なインフラとなった現在，ネットワークには高い信頼性が求められている．しかし，ネットワークにおいて単一リンク故障による経路切断が発生した際，もとの経路に比べて代替経路の経路長が大幅に増加し，通信品質の大幅な劣化を引き起こす可能性がある．これまで，既設ネットワークへの最小限のリンク増設によって，この経路長増加率を与えられた定数以下に抑えるネットワーク設計法を提案し，その有効性を示した．しかし，その設計法そのままでは新規ネットワークを構築する際には適用できない．本稿では，経路長増加率・直径・次数を制約として満たしつつ，コストに対応するリンク数が最小であるような新規ネットワークの設計問題を扱う．この問題がNP 完全であることを証明し，近似アルゴリズムを設計した．さらに，現実の様々なネットワークへ適用してアルゴリズムの有効性を評価した． |
| （英） | A telecommunication network should be reliable, since it is important as social infrastructure. But it is known that, in many real networks, there exists the risk that the quality of service drastically deteriorates when the length of paths increases by a link failure. To get rid of this risk, it is necessary to design a network that the maximum increasing rate of the length of all paths in a link failure is small. We proposed an approximation algorithm for a network design problem that constructs such a network by adding some links to a network in our previous paper. On the other hand, when we construct a network from scratch, we must consider not only the quality of the failure time but also that of the normal time. In this paper, we formalize this network design problem as the optimization problem that determines a graph with a constrained degree and diameter so that the maximum increasing rate of the lengths of all paths in an edge deletion is not more than a threshold. First, we prove that this problem is NP-complete. Next, we propose an approximation algorithm for this problem and evaluate its performance by applying the algorithm to some real ISP networks. As a result, the proposed algorithm shows the good performance. | |
| キーワード | （和） | 通信品質 / 経路長増加率 / 最適化問題 / NP 完全性 / 近似アルゴリズム / / / |
| （英） | quality of service / path length / optimization problem / NP-complete / approximation algorithm / / / | |
| 文献情報 | 信学技報, vol. 109, no. 448, NS2009-228, pp. 369-374, 2010年3月. | |
| 資料番号 | NS2009-228 | |
| 発行日 | 2010-02-25 (NS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2009-228 |
|
| 研究会情報 | |
| 研究会 | NS IN |
| 開催期間 | 2010-03-04 - 2010-03-05 |
| 開催地（和） | 宮崎シーガイア |
| 開催地（英） | Miyazaki Phoenix Seagaia Resort (Miyazaki) |
| テーマ（和） | 一般 |
| テーマ（英） | General, NS+IN workshop (March 4-5) |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2010-03-NS-IN |
| 本文の言語 | 日本語 |
| タイトル（和） | 故障時性能劣化が小さいリンク数最小ネットワーク設計法 |
| サブタイトル（和） | |
| タイトル（英） | Design Method of Smallest Robust Networks against Performance Deterioration during Failures |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 通信品質 / quality of service |
| キーワード(2)（和/英） | 経路長増加率 / path length |
| キーワード(3)（和/英） | 最適化問題 / optimization problem |
| キーワード(4)（和/英） | NP 完全性 / NP-complete |
| キーワード(5)（和/英） | 近似アルゴリズム / approximation algorithm |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 片山 希 / Nozomu Katayama / カタヤマ ノゾム |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 藤村 武史 / Takeshi Fujimura / フジムラ タケシ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 上山 憲昭 / Noriaki Kamiyama / カミヤマ ノリアキ |
| 第4著者 所属（和/英） | NTTサービスインテグレーション基盤研究所 (略称： NTT) NTT Service Integration Laboratories (略称： NTT) |
| 第5著者 氏名（和/英/ヨミ） | 長谷川 治久 / Haruhisa Hasegawa / ハセガワ ヒロヒサ |
| 第5著者 所属（和/英） | NTTサービスインテグレーション基盤研究所 (略称： NTT) NTT Service Integration Laboratories (略称： NTT) |
| 第6著者 氏名（和/英/ヨミ） | 吉野 秀明 / Hideaki Yoshino / ヨシノ ヒデアキ |
| 第6著者 所属（和/英） | NTTサービスインテグレーション基盤研究所 (略称： NTT) NTT Service Integration Laboratories (略称： NTT) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-03-05 09:50:00 |
| 発表時間 | 20分 |
| 申込先研究会 | NS |
| 資料番号 | NS2009-228 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.448 |
| ページ範囲 | pp.369-374 |
| ページ数 | 6 |
| 発行日 | 2010-02-25 (NS) |
[研究会発表申込システムのトップページに戻る]