電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2009-03-03 11:50
故障時における性能劣化を抑制するネットワーク設計法
片山 希藤村武史巳波弘佳関西学院大)・上山憲昭長谷川治久吉野秀明NTT
技報オンラインサービス実施中
抄録 (和) インターネットをはじめ,通信ネットワークが社会において必要不可欠なインフラとなった現在,ネットワークには高い信頼性が求められている.しかし,ネットワークにおいて単一リンク故障による経路切断が発生した際,もとの経路に比べて代替経路の経路長が大幅に増加し,通信品質の大幅な劣化を引き起こす可能性がある.通常,ネットワークは既に構築・運用されており,初期段階の想定から大幅に変化していることが多い.このような既設ネットワーク全体を再構築しなおすことは非現実的であるため,既存のネットワークに最小限の増設を行うことで性能を向上させること,つまり経路長増加率を小さくすることが必要となる.本稿では,これを経路長増加率を抑制する最小リンク付加問題として定式化した.そして,この問題が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. Such a network must be constructed by adding some links to a network, because it is impossible to reconstruct a network which is in operation.

In this paper, we formalize this network design problem as the optimization problem that determines the edges added to a graph 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 / backbone network / optimization problem / NP-complete / approximation algorithm / / /  
文献情報 信学技報, vol. 108, no. 457, NS2008-164, pp. 117-122, 2009年3月.
資料番号 NS2008-164 
発行日 2009-02-24 (NS) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 IN NS  
開催期間 2009-03-03 - 2009-03-04 
開催地(和) 沖縄残波岬ロイヤルホテル 
開催地(英) Okinawa-Zanpamisaki Royal Hotel 
テーマ(和) 一般 
テーマ(英) General issues 
講演論文情報の詳細
申込み研究会 NS 
会議コード 2009-03-IN-NS 
本文の言語 日本語 
タイトル(和) 故障時における性能劣化を抑制するネットワーク設計法 
サブタイトル(和)  
タイトル(英) A Design Method of Robust Networks against Performance Deterioration in Failures 
サブタイトル(英)  
キーワード(1)(和/英) 通信品質 / quality of service  
キーワード(2)(和/英) バックボーンネットワーク / backbone network  
キーワード(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)
第5著者 氏名(和/英/ヨミ) 長谷川 治久 / Haruhisa Hasegawa / ハセガワ ヒロヒサ
第5著者 所属(和/英) 日本電信電話株式会社 (略称: NTT)
NTT (略称: NTT)
第6著者 氏名(和/英/ヨミ) 吉野 秀明 / Hideaki Yoshino / ヨシノ ヒデアキ
第6著者 所属(和/英) 日本電信電話株式会社 (略称: NTT)
NTT (略称: 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著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2009-03-03 11:50:00 
発表時間 20 
申込先研究会 NS 
資料番号 IEICE-NS2008-164 
巻番号(vol) IEICE-108 
号番号(no) no.457 
ページ範囲 pp.117-122 
ページ数 IEICE-6 
発行日 IEICE-NS-2009-02-24 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会