計算量最小化を実現するk shortest simple pathアルゴリズム提案(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
k shortest pathアルゴリズムはネットワーク上での代替経路生成、複数経路を利用することによる負荷分散等への適用が期待される。方向性グラフ上でループレスなk shortest pathを生成するk shortest simple path生成アルゴリズムは、50年間の長きに渡り研究されているが、現状O(kmn)の計算量が最小である(nはノード数、mはリンク数)。本稿では、この計算量をO(km(log n+log k))に短縮するアルゴリズム(k-SPF)を提案するとともに、k-SPFアルゴリズムと既存のYenアルゴリズムを実装し、その処理時間を比較する。
- 社団法人電子情報通信学会の論文
- 2010-12-09
著者
関連論文
- EJBによるレイヤ1VPNカスタマNMSの実装(GMPLS管理,情報通信マネジメント,一般)
- P2MP TEに適用するSteiner Treeアルゴリズムの検討(次世代・新世代ネットワークアーキテクチャ,トラヒック計測・制御,サービス品質,ネットワーク管理,一般)
- 階層分散型NMSを用いたGMPLS網ルーティング方式(セッション4)
- B-7-71 新K Shortest Path生成アルゴリズムによる計算量削減(B-7.情報ネットワーク,一般セッション)
- B-6-54 IPTVに適用するP2MP Tree生成アルゴリズムの検討(B-6.ネットワークシステム,一般セッション)
- B-6-128 マルチパスを利用したセンサートラフィック分散方式の提案(B-6.ネットワークシステム,一般セッション)
- B-14-12 VPN単位の管理を導入したL1-VPN管理システム(B-14. テレコミュニケーションマネジメント,一般セッション)
- GMPLSパス構成/故障管理手法(次世代ネットワークアーキテクチャ,次世代ネットワークのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,一般)
- B-6-37 階層分散型PCEによるマルチキャストTraffic Engineering手法の提案(B-6.ネットワークシステム,一般講演)
- 階層分散型PCEによるマルチキャストツリー生成アルゴリズムの提案
- B-7-72 エンドツーエンドQoSを保証するGMPLS VPN管理法の提案(B-7.情報ネットワーク,一般講演)
- IM2005国際会議報告(設備管理, ネットワーク管理, 及び一般)
- 階層分散型NMSを用いたGMPLS網ルーティング方式(セッション4)
- BS-3-6 高速マルチパス生成を実現するk shortest simple pathアルゴリズム提案と実装評価(BS-3.次世代ICTインフラの実現に向けたネットワーク制御・管理技術,シンポジウムセッション)
- B-7-26 方向性Steinerアルゴリズムの計算量最小化検討(B-7.情報ネットワーク,一般セッション)
- 新k shortest simple pathアルゴリズムによる平均時間計算量削減
- 計算量最小化を実現するk shortest simple pathアルゴリズム提案(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- B-14-16 センター集中型サービスに適用するマルチパス方式の検討(B-14. 情報通信マネジメント,一般セッション)
- 新マルチパス生成アルゴリズムを利用したVoD配信ネットワークの実現(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- マルチキャストパスコストとネットワークリソースを最適化するSteinerアルゴリズムの検討(ネットワーク管理,ネットワーク品質,一般)
- マルチキャストパスコストとネットワークリソースを最適化する Steiner アルゴリズムの検討
- P2MP-TEに適用する新Steiner treeアルゴリズムの提案(サービス管理,運用管理技術,セキュリティ管理,及び一般)
- Steiner treeの省エネルギールーティングへの適用検討(ホームネットワーク,ユビキタスネットワーク,クラウドコンピューティング,コンテキストアウェア,位置情報サービス,e-コマース及び一般)
- D-1-2 Steiner treeアルゴリズムBBMCの平均時間計算量解析(D-1.コンピュテーション)
- P2MP-TEに適用する新 Steiner tree アルゴリズムの提案