文献

J-GLOBAL ID：201702216566464752   整理番号：17A0540542

分断確率を考慮したリンク保護に基づく高信頼ネットワーク設計法

Method for Finding Protected Links to Keep Robust Network against Link Failure Considering Failure Probability

著者 (3件)： 宇治槻 (関西学院大 理工) ,  井上萌子 (関西学院大 理工) ,  巳波弘佳 (関西学院大 理工)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 484(NS2016 157-253)  ページ： 157-162  発行年： 2017年02月23日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ネットワークには高い信頼性が求められており,ネットワーク故障に耐性のある頑健なネットワークの構築が重要である。特にコンテンツ配信サービスにおいては,サービスを受けるノードとサーバとの通信経路の切断によるサービス途絶の可能性をできるだけ抑えなければならない。コンテンツ配信には,元のコンテンツを有するマスタサーバと,そのコピーを保有してユーザからのアクセスを受ける多数のエッジサーバが用いられることが多いが,故障時においてもマスタサーバとエッジサーバの間に通信経路が存在するような信頼性がネットワークには必要である。リンク故障に耐性のある頑健なネットワークの構築のため,バックアップ機構や高速復旧機構などによってリンクの故障率を大幅に下げてリンクの信頼性を高める(リンク保護)ことが必要であるが,そのような高信頼性ネットワークの構築には膨大なコストがかかる。そのため,必要性の高いリンクのみを優先的に保護することが現実的である。ここで必要性の高いリンクとは,そのリンクの故障により,迂回経路がとれず通信が途絶するなど著しく性能が劣化するものを指す。本稿ではさらに,リンク故障の確率を考慮する。リンク故障確率は必ずしも一律ではない。そこで,リンク故障確率と保護の必要性の多寡を考慮して,限られたコストの下で有効な保護リンクを決定することが必要である。つまり,保護リンク以外のリンクが故障し,マスタサーバとエッジサーバ間の通信が継続できなくなる確率が最小となるように保護リンクを決定する最適化問題を扱う。つまり,コスト制約(保護リンク数制約)の下で,分断確率が最小となるように保護リンクを決定する問題である。本稿では,このネットワーク設計問題を定式化し,NP困難性を示した。さらに,ヒューリスティックアルゴリズムを設計し,様々な現実ネットワークトポロジに対して性能評価を行った。(著者抄録)

シソーラス用語： *分割 ,  *確率 ,  *リンク ,  *保護 ,  *信頼性 ,  *設計 ,  通信網 ,  フォールトトレランス ,  情報配布 ,  計算機システム ,  端部 ,  ロバスト性 ,  故障率 ,  最適化問題 ,  NP困難 ,  発見的方法
準シソーラス用語： *通信リンク ,  *高信頼性 ,  *ネットワーク設計 ,  コンテンツ配信 ,  サーバ【計算機】

分類 (1件)： 通信網  (ND07030A)

引用文献 (12件)：

• A. Frank, ′′Augmenting graphs to meet edge-connectivity requirements,′′ Proc. 31st Annual Symposium on Foundations of Computer Science, St. Louis, 22-24.Oct., 1990.
• T. Ishii and M. Hagiwara, ′′Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs,′′ Discrete Applied Mathematics, Vol. 154, No. 16, pp. 2307-2329, 2006.
• G. Kortsarz, R. Krauthgamer, J. R. Lee, ′′Hardness of approximation for vertex-connectivity network design problems,′′ Lecture Notes in Computer Science, Vol. 2462, pp. 185-199, 2002.
• A. Arulselvan, C. W. Commander, L. Elefteriadou, P. M. Pardalos, ′′Detecting Critical Nodes in Sparse Graph,′′ Proc. Computers & Operations Research, Vol. 36, Issue 7, pp. 2193-2200, Jul., 2009.
• K. Imagawa, T. Fujimura, H, Miwa ′′Approximation Algorithms for Finding Protected Links to Keep Small Diameter Against Link Failures′′, Proc. International Conference on Intelligent Networking and Collaborative System (INCoS2011), Fourth International Workshop on Information Network Design (WIND2011), Fukuoka, Japan, Nov.30 Dec.1-2, 2011.

タイトルに関連する用語 (4件)： 分断 ,  確率 ,  リンク ,  設計法