リンク故障時の直径増加を抑制する保護リンク決定問題に対する近似アルゴリズム(網構成・理論)
スポンサーリンク
概要
- 論文の詳細を見る
インターネットが重要な社会基盤となるにともない,その信頼性,品質への要求は高くなっている.ネットワーク遅延はそのようなネットワーク品質のひとつであり,2ノード間の遅延はそれらの距離と相関があるため,ネットワークの直径,つまり全ての2ノード間の距離の最大値は小さいことが望ましい.さらに,ネットワークの故障に対して遅延を小さく保つ必要がある.そのため,故障によって著しい品質劣化を引き起こすような致命的なリンクは,IP層以上のネットワークで故障を感知できないように,迅速に修復を行うことで保護しなければならない.そのような保護されるリンクの数は設備と運用にかかるコストを抑えるためにできる限り少ないことが望ましい.そのため,保護されていないリンクの故障に対してネットワークの直径が一定の数値より大きくならないような最小数の保護すべきリンクを求めることが重要である.本稿では,この問題におけるこれらの未解決であった問題を解決した.まず,この問題はk=2に限定してもNP困難であることを証明した.さらに,kが2以上の定数である場合において,定数の近似度をもつ多項式時間近似アルゴリズムを与えた.これらの結果はこの問題の計算複雑性を理論的に明らかにし,実用的なネットワーク設計アルゴリズムを与えた.
- 一般社団法人電子情報通信学会の論文
- 2012-03-01
著者
-
藤村 武史
関西学院大学理工学部
-
巳波 弘佳
(現)関西学院大学理工学部情報科学科
-
巳波 弘佳
関西学院大学 理工学部 情報科学科
-
巳波 弘佳
関西学院大 理工
-
今川 廣二
関西学院大学理工学部情報科学科
-
藤村 武史
関西学院大学
-
今川 廣二
関西学院大学大学院理工学研究科情報科学専攻
関連論文
- リンクメトリック最適化によるネットワーク負荷分散制御 (ネットワークシステム)
- 3.ランダムウォークの数理に学ぶ : DTN(Delay-and Disruption-Tolerant Network)における移動体無線通信と情報収集時間分布(情報通信ネットワークの設計・制御理論の新潮流-異分野からのアプローチ-)
- インターネットにおけるべき乗則(複雑ネットワークの世界-ネットワーク研究の新展開-)
- 故障時性能劣化が小さいリンク数最小ネットワーク設計法 (ネットワークシステム)
- 故障時における性能劣化を抑制するネットワーク設計法(ルーティング,ネットワーク設計)
- フォトニックMPLSネットワークにおけるパス設計
- スポット型通信を用いた高速移動体へのデータ送信方式の提案と評価
- 故障時性能劣化が小さいリンク数最小ネットワーク設計法(ネットワーク管理/制御/設計)
- 構造型P2Pネットワークにおける次数制約付きブロードキャスト制御法(クラウド、グリッド・P2P)
- リンクメトリック最適化によるネットワーク負荷分散制御(ルーティング・低消費電力化)
- 2-C-7 重量付モジュール詰め込みの最適化(組合せ最適化)
- 1-A-4 段ボールの製造工程における順序づけ問題(離散最適化(2))
- 通信トラヒック分析による人間関係のトポロジ構造とクラスタ構造に関する考察
- 通信トラヒック分析による人間関係のトポロジ構造とクラスタ構造に関する考察
- 通信トラヒック分析による人間関係のトポロジ構造とクラスタ構造に関する考察
- 通信トラヒック分析による人間関係のトポロジ構造とクラスタ構造に関する考察
- モーションキャプチャを用いたピアノ演奏動作のCG表現と音楽演奏インタフェースへの応用(コンテンツ生成,音楽インタフェース)
- 極値理論による閾値モデル解析と普遍的冪乗則(ネットワークモデル)
- AI-2-2 乗客の待ち時間抑制を重視したマルチカーエレベータ運行制御アルゴリズム(AI-2.CSTソリューションコンペティション2008:表彰式・シンポジウム,ソサイエティ企画)
- 次数・直径の小さいP2Pネットワーク構成法とその評価(P2Pとオーバーレイ(2))
- P2Pにおける次数・直径の小さいオーバレイネットワーク構成法(P2P及びオーバレイネットワーク, 無線ネットワーク,アドホックネットワーク,センサネットワーク及び一般)
- 劣通信環境における情報収集とその構造推定への応用
- 知っておきたいキーワード(第53回)DTN(Delay-Disruption-Disconnect-Tolerant Networking)
- 劣通信環境下における効率的な地図構築のための群ロボット探索アルゴリズム(安全・安心(災害時通信))
- 劣通信環境下における協調型地図推定(安全・安心(災害時通信))
- 移動センサ感染型情報共有過程における情報収集の緩和時間(センサーネットワーク)
- B-7-34 通信トラヒック分析による人間関係トポロジのクラスタ構造(B-7. 情報ネットワーク, 通信2)
- 蓄積運搬転送型通信を効率化するVirtual Segment方式におけるベースノード配置法(アドホックネットワーク,センサネットワーク)
- 信頼性と効率性を考慮したサーバ群配置法(ルーティング,ネットワーク設計)
- 高速移動体へのコンテンツ配信制御方式(映像配信)
- 信頼性と効率性を考慮したパス制御法およびネットワーク設計法(NW管理,次世代NWアーキテクチャ,次世代NWのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,次世代NWサービス品質,一般)
- 特集にあたって(複雑ネットワークの世界-ネットワーク研究の新展開-)
- 21pVC-12 情報共有過程における情報収集時間分布のベキ指数についての考察(21pVC 確率過程・確率モデル,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 移動センサの情報共有過程における効率的な情報収集アルゴリズム(センサネットワーク)
- 移動センサ情報共有過程における情報収集時間分布(センサネットワーク)
- バックボーンネットワークの信頼性に関する分析(ネットワーク一般)
- 限定されたリンク集合におけるメトリック更新によるトラヒック制御 (電子情報通信における萌芽的研究論文小特集)
- 人間関係のグラフ構造とその振舞いについて(IPv6, インターネットの品質制御技術及び一般)
- AT-3-1 劣通信環境における情報収集とその応用(AT-3.コンカレントシステム理論の新しい流れ,チュートリアルセッション,ソサイエティ企画)
- 3ZC-8 効率的な地図構築のための群ロボット探索戦略(災害時通信,学生セッション,ネットワーク,情報処理学会創立50周年記念)
- 2N-7 高い耐故障性と低いネットワーク負荷を実現するサーバ配置に関する研究(グラフやネットワークに関するアルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 2N-8 ネットワーク負荷分散制御のためのリンクメトリック最適化(グラフやネットワークに関するアルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- スケールフリー性を持つ閾値モデルの諸特性量の解析(P2P及びオーバレイネットワーク, 無線ネットワーク,アドホックネットワーク,センサネットワーク及び一般)
- 25pYB-10 頂点重みの相互作用による非成長型スケールフリー・ネットワークモデル(力学系(振動子・その他),領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 大規模高速ネットワークにおける信頼性と効率性を考慮したパス制御法(GMPLS・ネットワーク管理)
- 21aTP-8 Zebranet確率モデルにおける情報収集時間分布(生物・生態系(社会・言語・ゲーム等含む)1,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- 故障時のネットワーク負荷集中を回避する高信頼リンク決定法 (ネットワークシステム)
- サーバとネットワークへの負荷集中を回避するサーバ配置 (ネットワークシステム)
- 限定されたリンク集合におけるメトリック更新によるトラヒック制御(研究速報, 電子情報通信における萌芽的研究論文)
- ピアノ演奏CGアニメーションの自動生成 : 演奏モーションのヒューマナイズとGPUレンダリング(学生研究発表会)
- DTN 技術の現状と展望
- モーションキャプチャと筋電図計測を用いたピアノ演奏における連続指運動スキルの解明(学生研究発表会)
- 劣通信環境下における協調型地図推定
- 26aTD-10 モバイル無線通信実験におけるすれ違い頻度分布と一期一会の意味(26aTD ネットワーク一般1,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- マルチカーエレベータにおける運行自由度を考慮した効率的制御方法(CSTソリューションコンペティション2010,コンカレントシステム及び一般)
- Bluetooth&Wi-Fiモバイル無線通信実験とすれ違い頻度分布の冪乗則 : 一期一会の影響(NW制御(1))
- 故障時のネットワーク負荷集中を回避する高信頼リンク決定法(NWシステム(信頼性))
- サーバとネットワークへの負荷集中を回避するサーバ配置(NWシステム)
- ユーザの利用傾向に基づく非構造型自律形成P2Pネットワーク制御(P2P)
- サーバへの可到達性を保障する高信頼リンク決定法(NWシステム(信頼性))
- 劣通信環境におけるノードの移動特性を考慮した中継転送方式(NW制御(1))
- サンプリングに基づくフローサイズ分布推定法(トラヒック解析・制御(4))
- ピアノ演奏CGアニメーションの自動生成 : 演奏モーションのヒューマナイズとGPUレンダリング
- モーションキャプチャと筋電図計測を用いたピアノ演奏における連続指運動スキルの解明
- 22aGU-7 一期一会 : 不平等でスケールフリーな人の出会い(22aGU 生物・生態系・経済物理学1,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 効率的かつ高信頼な通信ネットワーク設計の研究の流れ(ネットワークアーキテクチャ(オーバレイ,P2P,ユビキタスNW,スケールフリーNW,アクティブNW,NGN・新世代NW),次世代パケットトランスポート(高速Ethernet,IP over WDM,マルチサービスパケット技術,MPLS),グリッド,一般)
- 2-K-8 ピアノ演奏CG自動生成システムとその適用例(ワークショップ「娯楽のOR-エンターテイメントの数理」)
- 最適キャッシュ配置に基づくクエリ誘導方式 (ネットワークシステム)
- リンク故障時の直径増加を抑制する保護リンク決定問題に対する近似アルゴリズム (ネットワークシステム)
- 劣通信環境下における災害救助エージェントの組織
- すれちがい通信を利用したリアルタイム災害時避難誘導 (情報ネットワーク)
- 2-C-9 コンピュータグラフィックスによるピアノ演奏動作と発音時刻の同期
- 2-F-7 ネットオークションにおけるコンサートチケットの価格分析(金融(1))
- 2-A-11 災害発生時において避難場所への物資配送を効率化するための道路復旧問題
- 東日本大震災時の実道路網トポロジに基づくVirtual Segment方式の性能評価(障害復旧)
- 最適キャッシュ配置に基づくクエリ誘導方式(コンテンツ配信)
- 故障時においてもサーバへの可到達性と距離を保障する高信頼リンク決定法(網設計)
- 侵入者検知のためのセンサ配置問題(ホームネットワーク)
- コグニティブ無線ネットワークにおけるマルチキャストルーティング制御アルゴリズム(無線メッシュNW)
- 故障時においても直径が抑制されたリンク数の少ないネットワーク設計法(網構成・理論)
- すれちがい通信を利用したリアルタイム災害時避難誘導(災害対策)
- 輻輳抑制を考慮した省電力ネットワーク制御法(省電力ネットワーク)
- 26pBG-6 一期一会(その2) : 出会いの凝集現象とスケールフリー性の理論的理解(26pBG 生物・生態系2・ネットワーク一般,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- 劣通信環境におけるフローサイズ分布を考慮したマルチパス制御方式(無線メッシュNW)
- Path splicing制御方式におけるリンク容量を考慮した全域木集合決定法(網設計)
- リンク故障時の直径増加を抑制する保護リンク決定問題に対する近似アルゴリズム(網構成・理論)
- ピアノ演奏コンピュータグラフィクス制作技術(娯楽のOR)
- すれちがい通信を利用した災害時避難誘導法(震災復興や新興国の近未来に役立つ情報ネットワーク技術論文)
- ヒューマンモビリティモデルとそれに基づく移動経路推定法(位置情報)
- すれちがい通信を利用した避難誘導における混雑地周辺での迂回経路選択の影響(センサNW2)
- バッテリ長寿命化のためのセンサネットワーク設計問題(センサNW)
- 災害時避難誘導システムにおける最速避難経路決定問題(位置情報)
- ノード破壊によるネットワーク分断を抑制する保護ノード決定法(網設計信頼性)
- 2リンク同時故障に対してサーバへの可到達性を高く保つ保護リンク決定法(ネットワーク分析・理論)
- 故障時においてもサーバへの可到達性を保障し距離増大を抑制する高信頼リンク決定法(ネットワーク分析・理論)
- 故障時の通信経路長増加を抑制する高信頼リンク決定法(網設計信頼性)
- サーバ障害を考慮したデータセンタ高信頼化設計法(網設計マルチレイヤ)
- 無人ヘリによる道路・鉄道網の被災情報収集経路決定法(ルーティング)
- 災害時のVirtual Segment方式におけるベースノード復旧順序決定法(NW運用)
- 故障時においても直径が抑制されたリンク数の少ないネットワーク設計法