講演名 | 2014-07-09 タイセット基底の局所的操作による点素パスの算出について(システムと信号処理及び一般) 伊藤 隆太, 篠宮 紀彦, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 情報通信ネットワークのノード障害に対応した迂回パスは,現用パスに対し点素である必要がある.また,障害ノードに隣接する2つのノードを結び,現用パスに対して点素であるパスを局所的な点素パスと呼び,局所的な点素パスを用いる復旧は高速な障害復旧につながる可能性があることが示されている.そこで本稿では,局所的な点素パスの効率的な算出について述べる.局所的な点素パスの算出には,閉路を構成する辺集合をタイセットとし,排他的論理和が1つのタイセットになるタイセット集合を用いる.しかし,任意の複数のタイセットの排他的論理和が1つのタイセットになるとは限らない.そこで,2つのタイセットの排他的論理和が1つのタイセットとなる十分条件として利用可能な概念である重複度を導入し,重複度に関する性質について示す.また,提案手法と局所的な点素パスを最短パスアルゴリズムを用いて算出する手法との比較結果を示す. |
抄録(英) | In the information communication network, it is required for a detour path to be node-disjoint regarding a working path in case of a node failure occurs. Additionally, the previous research has indicated that fast failure recovery might be realized by using local node-disjoint paths that connect two nodes neighboring the failure node. This paper discusses a calculation method of local node-disjoint paths. By defining an edge set which forms a cycle as a tie-set, local node-disjoint paths are calculated by using tie-sets whose exclusive-OR leads to a single tie-set. However, an exclusive OR of arbitrary tie-sets is not always a tie-set. Hence, this paper proposes the concept of overlapping degree as a sufficient condition that an exclusive-OR of two tie-sets must becomes a tie-set and discusses its property. Finally, this paper shows the comparison results of a proposed method and a simple method using shortest path algorithm. |
キーワード(和) | タイセットベクトル空間 / 排他的論理和 / 点素パス / グラフ理論 |
キーワード(英) | tie-set vector space / exclusive OR / node-disjoint path / graph theory |
資料番号 | CAS2014-9,VLD2014-18,SIP2014-30,MSS2014-9,SIS2014-9 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2014/7/2(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | JPN |
タイトル(和) | タイセット基底の局所的操作による点素パスの算出について(システムと信号処理及び一般) |
サブタイトル(和) | |
タイトル(英) | On finding node-disjoint paths by local manipulation of a tie-set base |
サブタイトル(和) | |
キーワード(1)(和/英) | タイセットベクトル空間 / tie-set vector space |
キーワード(2)(和/英) | 排他的論理和 / exclusive OR |
キーワード(3)(和/英) | 点素パス / node-disjoint path |
キーワード(4)(和/英) | グラフ理論 / graph theory |
第 1 著者 氏名(和/英) | 伊藤 隆太 / Ryuta ITO |
第 1 著者 所属(和/英) | 創価大学工学部 Faculty of Engineering, Soka University |
第 2 著者 氏名(和/英) | 篠宮 紀彦 / Norihiko SHINOMIYA |
第 2 著者 所属(和/英) | 創価大学工学部 Faculty of Engineering, Soka University |
発表年月日 | 2014-07-09 |
資料番号 | CAS2014-9,VLD2014-18,SIP2014-30,MSS2014-9,SIS2014-9 |
巻番号(vol) | vol.114 |
号番号(no) | 123 |
ページ範囲 | pp.- |
ページ数 | 4 |
発行日 |