リンクディスジョイント経路計算の高速解法の一検討 : DAPDNA-2による並列マルチレイヤ経路計算
スポンサーリンク
概要
- 論文の詳細を見る
K Disjoint-Paths Pairs (KDPPs)は,耐障害性を確保するためのリンクディスジョイント経路を求めるアルゴリズムとして広く使用されているが,最適解(合計コストが最小となるリンクディスジョイント経路の組)が得られない場合が存在することが知られている.しかし,最適解が得られない状況について,詳しく言及している過去の研究はほとんど存在しない.そこで,本稿では,計算機シミュレーションを用いて様々なトポロジにおけるKDPPsの解の精度を定量化する.さらに,並列リコンフィギャラブルプロセッサに適したマルチレイヤを考慮するリンクディスジョイント経路探索アルゴリズムも提案し,提案アルゴリズムがKDPPsと比較して計算クロック数を最大で約99.6%減少させることを示す.
- 社団法人電子情報通信学会の論文
- 2008-08-01
著者
-
荒川 豊
慶應義塾大学理工学部情報工学科
-
山中 直明
慶應義塾大学理工学部情報工学科
-
高 山
慶應義塾大学理工学研究科
-
木原 拓
慶應義塾大学理工学研究科
-
清水 翔
慶應義塾大学理工学研究科
-
山中 直明
慶應義塾大学
-
高 山
慶應義塾大学理工学部情報工学科
-
清水 翔
慶應義塾大学理工学部情報工学科
-
木原 拓
慶應義塾大学理工学部情報工学科
-
高 山
慶應義塾大学大学院理工学研究科
関連論文
- 連続送信型フレームを用いたアクティブ光アクセスネットワークのレンジング方式(研究速報)
- uGridにおけるセキュリティを考慮したマルチサービス映像配信ネットワークの提案(フォトニックネットワーク関連技術,一般)
- uGridにおけるダイナミック光パスを用いた映像サービスパーツ選択(フォトニックネットワーク関連技術,一般)
- コンテンツ配信網におけるコンテンツサーバの負荷軽減のための階層型協調分割ダウンロード方式(IPバックボーンネットワーク,MPLS,GMPLS,フォトニックネットワーク,トラヒック制御・解析及び一般)
- 大容量データ転送アプリケーションの実現に向けたTCP over SCTPパラレルネットワーキングおよび並列経路選択手法の検討
- GMPLSシグナリングによるE-tree確立に向けたRSVP-TE拡張の実装(IPバックボーンネットワーク、MPLS、GMPLS、フォトニックネットワーク及び一般)
- 広域分散コンピューティングを用いた遅延を考慮したスケールフリーディスプレイ構築法(IPバックボーンネットワーク,MPLS,GMPLS,フォトニックネットワーク,トラヒック制御・解析及び一般)
- ダイナミックリコンフィギュラブルプロセッサDAPDNA-2上のオンチップ仮想ネットワークによる新しいネットワーク最適化手法(リコンフィギャラブル応用,デザインガイア2008-VLSI設計の新しい大地)
- 5-1 電子情報通信学会の国際化とIEEEとの協業の経験(5.学会における国際交流活動,私の国際交流の経験)
- 簡易型多地点雷観測システムの実験(ユビキタス・センサネットワークを支える理論,一般)
- 光ネットワークの省電力化へ向けたリソース最小化アルゴリズム(フォトニックネットワークシステム,光ルーティング,ブロードバンドアプリケーション,一般)
- BS-8-10 ゾーン内最適化およびエリア内最適化に基づく電力消費量最適化アーキテクチャの提案(BS-8.情報通信とエネルギー管理の統合技術,シンポジウムセッション)
- 次世代広域レイヤ2ネットワークの実現へ向けたフレキシブルスイッチの提案と検証(フォトニックネットワーク/制御,光制御(波長変換・スイッチング等),光波/量子通信,GMPLS,アクセス網技術,一般)
- 同時受け付けポート数を考慮した選択的パケット廃棄法の提案
- 同時受け付けポート数を考慮した選択的パケット廃棄法の提案
- ベイズ推測を用いた不正侵入イベント増減予測(ネットワークセキュリティ)
- 無線アドホックネットワークに適したルーチング情報を用いたオンデマンド公開鍵分散管理方式(情報セキュリティ応用)
- B-7-18 イベント検知方向に注目したIDSログ異常分析手法の提案(B-7. 情報ネットワーク)
- B-7-11 不正侵入イベントの増減予測を行うためのベイズ推測の適用検討(B-7. 情報ネットワーク)
- 無線アドホックネットワークに適したオンデマンド公開鍵分散管理方式(セッション10)
- 無線アドホックネットワークに適したオンデマンド公開鍵分散管理方式(セッション10)
- 入力位置情報を付加したパスワード認証方式
- GMPLSによる動的パス切り替えを利用した次世代P2Pネットワーク(フォトニックネットワークシステム,光ルーティング,ブロードバンドアプリケーション,一般)
- レーザ生誕50周年を迎えて(学生/教養のページ)
- MPLS網において低帯域幅消費を実現する複数P2MP LSPを用いたマルチキャスト電子透かし方式(グリーンICTとQoE,一般)
- アクティブ光アクセスネットワークにおける2系統の光ツリーによるプロテクション方式(フォトニックネットワーク関連技術,一般)
- バースト転送を用いたミラーサーバ自動選択型プリフェッチプロトコルプロキシの提案
- 連続送信型フレームを用いたアクティブ光アクセスネットワークのレンジング方式
- アクティブ光アクセスネットワークにおけるTCPスループットを考慮したパラメータ設計および動的スロット割当(フォトニックネットワーク関連技術,一般)
- 全光ネットワークにおける四光波混合を考慮した分散波長割り当て方式(フォトニックネットワーク関連技術,一般)
- 広域レイヤ2ネットワークにおける遅延揺らぎの小さいキューイング方式(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 広域レイヤ2ネットワークにおける遅延揺らぎの小さいキューイング方式(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 広域レイヤ2ネットワークにおける遅延揺らぎの小さいキューイング方式(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 次世代広域レイヤ2網実現に向けたプロトコル実装と実証実験(ネットワーク制御,波長多重ネットワーク技術,光ノード技術,WDM技術,光LAN技術,光信号処理技術,一般)
- 新世代広域レイヤ2網におけるアドレッシング及びエッジクロスコネクション設定手法の検討
- アクティブ光スイッチを用いた光アクセス網の一検討
- ユビキタスネットワーキング環境(uGrid)におけるスケーラブルなサービス提供の実現へ向けたルーチングプロトコルの拡張(ポストIPネットワーキング,ネットワークモデル,インターネットトラヒック,TCP/IP,マルチメディア通信,ネットワーク管理,リソース管理,プライベートネットワーク, NW安全性,及び一般)
- B-8-31 アクティブ光アクセスシステムにおける光スイッチエレメントの評価(B-8.通信方式,一般セッション)
- B-12-4 新世代広域レイヤ2網のアドレッシング手法の考察(B-12.フォトニックネットワーク,一般セッション)
- GMPLS制御によるPLZT超高速光スイッチを用いた光スロット交換ネットワークの提案と実装
- λグリッドネットワークにおいてデッドラインを考慮した波長割り当てスケジューリング
- PLZT超高速光スイッチを用いて動的パス切り替えを行う光スロット交換(OSS:Optical Slot Switching)
- OCBSにおいてあて先エッジルータまでのホップ数に依存しないQoS制御を実現するバースト信号生成方式(光集積回路/素子, スイッチング, PLC, ファイバ型デバイス, 導波路解析, 一般)
- OCBSにおいてあて先エッジルータまでのホップ数に依存しないQoS制御を実現するバースト信号生成方式(光集積回路/素子, スイッチング, PLC, ファイバ型デバイス, 導波路解析, 一般)
- OCBSにおいてあて先エッジルータまでのホップ数に依存しないQoS制御を実現するバースト信号生成方式(光集積回路/素子, スイッチング, PLC, ファイバ型デバイス, 導波路解析, 一般)
- OCBSにおいてあて先エッジルータまでのホップ数に依存しないQoS制御を実現するバースト信号生成方式(光集積回路/素子, スイッチング, PLC, ファイバ型デバイス, 導波路解析, 一般)
- 光バースト交換に基づくバースト・サーキット融合型ネットワーク(IPバックボーンネットワーク, フォトニックネットワークの構成/管理/制御プロトコル技術及び一般)
- リンクパワーオフによるネットワーク省電力化のための高速トポロジ計算手法(グリーンICTとQoE,一般)
- リンクパワーオフによるネットワーク省電力化のための高速トポロジ計算手法(グリーンICTとQoE,一般)
- B-12-5 MiDoRi GMPLSプロトコル拡張の提案(B-12.フォトニックネットワーク,一般セッション)
- ユビキタスグリッドネットワーキング環境(uGrid)実現に向けたサービスパーツ間接続実験(フォトニックネットワーク関連技術,一般)
- ユビキタスグリッドネットワーキング環境(uGrid)の研究提案(PN一般セッション,IPバックボーンネットワーク,MPLS,GMPLS,フォトニックネットワーク及び一般)
- 太陽追跡型データセンタ実現のための仮想マシン移行方式の一検討(IPバックボーンネットワーク,MPLS,GMPLS,フォトニックネットワーク及び一般)
- 並列プロセッサDAPDNA-2を用いたリンクディスジョイント経路計算の高速解法(アプリケーション2,FPGA応用及び一般)
- 並列プロセッサDAPDNA-2を用いたリンクディスジョイント経路計算の高速解法(アプリケーション2,FPGA応用及び一般)
- 並列プロセッサDAPDNA-2を用いたリンクディスジョイント経路計算の高速解法(アプリケーション2,FPGA応用及び一般)
- 並列プロセッサDAPDNA-2を用いたリンクディスジョイント経路計算の高速解法(アプリケーション2,FPGA応用及び一般)
- BS-9-9 GMPLS制御イーサネットにおけるインバンド通信チャネル実現方式(BS-9.テラビットLAN/MANを実現する光波長アクセス技術,シンポジウムセッション)
- GMPLS制御イーサネットにおけるインバンド通信チャネルの実装と実証実験
- リンクディスジョイント経路計算の高速解法の一検討 : DAPDNA-2による並列マルチレイヤ経路計算
- 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法(FPGAの応用)
- 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法(FPGAの応用)
- ネットワークの低消費電力化に向けた網再構成手法
- 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法(FPGAの応用)
- 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法(FPGAの応用)
- GMPLSにおける予約可能資源情報の高速な伝播方法
- 並列リコンフィギュラブルプロセッサDAPDNA-2を用いた最短経路探索
- リコンフィギュラブルプロセッサを用いた最短経路探索に関する一検討(ネットワーク, デザインガイア-VLSI設計の新しい大地を考える研究会-)
- サーバ-クライアント協調型P2Pコンテンツ配信ネットワークシステムの検討および実装(フォトニックネットワーク関連技術,一般)
- P2Pを用いた高品位映像配信に向けた帯域考慮型オーバレイ再構築方式
- ロングテール化するユーザリクエストを効率的に処理するコンテンツ配信ネットワークシステム
- コンテンツ配信におけるスケジューリング・マルチキャストの一検討(VoIP・IPマルチキャスト,ホームネットワーク,オーバーレイネットワーク,RFID及び一般)
- パラレル伝送を適用したグリッドコンピューティング特性の評価(フォトニックネットワーク関連技術,一般)
- λグリッドネットワークにおける分散データアクセス手法(フォトニックネットワーク/制御,光制御(波長変換・スイッチング等),光波/量子通信,GMPLS,一般)
- 変換範囲が制限された波長変換器を用いた WDM ネットワークにおける波長割当方式
- 変換範囲が制限された波長変換器を用いた WDM ネットワークにおける波長割当方式
- 変換範囲が制限された波長変換器を用いたWDMネットワークにおける波長割当方式
- TTFR型光バースト交換リングネットワークにおけるメディアアクセス制御方式(MP(Lambda)S,フォトニックネットワーク/制御,光波長変換・スイッチング,一般)
- TTFR型光バースト交換リングネットワークにおけるメディアアクセス制御方式(MP(Lambda)S,フォトニックネットワーク/制御,光波長変換・スイッチング,一般)
- TTFR型光バースト交換リングネットワークにおけるメディアアクセス制御方式(MP(Lambda)S,フォトニックネットワーク/制御,光波長変換・スイッチング,一般)
- 光グリッドにおける優先度及びジョブ終了時間を考慮したジョブスケジューリング方式の提案
- B-7-15 ユビキタスグリッドネットワーキング環境(uGrid)の提案(B-7.情報ネットワーク,一般講演)
- 部分廃棄を適用した光バースト交換網において複合バースト信号を用いた優先制御方式(ネットワーク)
- OCBSネットワークにおいてIPパケット長を考慮したバースト生成方式
- OCBSネットワークにおいてIPパケット長を考慮したバースト生成方式
- OCBSネットワークにおいてIPパケット長を考慮したバースト生成方式
- OBSネットワークにおいてバースト信号長制御,オフセット時間制御,部分廃棄を組み合わせたQoS差別化方式(光ファイバ伝送)
- OCBSネットワークにおいてあて先エッジルータまでのホップ数を考慮したバースト信号棄却方式(交換)
- OBSネットワークにおいてパケット棄却率及びパケット遅延に対する品質要求を考慮したQoS制御方式(NW性能管理,品質とコスト,品質と感性,一般)
- OBSネットワークにおいてパケット棄却率及びパケット遅延に対する品質要求を考慮したQoS制御方式(NW性能管理,品質とコスト,品質と感性,一般)
- OBSネットワークにおいてパケット棄却率及びパケット遅延に対する品質要求を考慮したQoS制御方式(NW性能管理,品質とコスト,品質と感性,一般)
- OBSネットワークにおいてパケット棄却率及びパケット遅延に対する品質要求を考慮したQoS制御方式
- OCBSネットワークにおいて宛先エッジルータまでのホップ数を考慮したバースト信号棄却方式(セッション8)
- OCBSネットワークにおいて宛先エッジルータまでのホップ数を考慮したバースト信号棄却方式
- OBSネットワークにおけるOn-the-flyパス構築を用いたQoS差別化方式(フォトニックネットワーク(IP+オプティカル)システム, 光ルーティング技術, 一般)
- 嗜好性を考慮したPeer-to-Peerオーバーレイネットワーク
- 次世代広域レイヤ2ネットワークの実現へ向けたフレキシブルスイッチの提案と検証
- BCS-1-4 高速光スイッチのネットワークへの応用技術(BCS-1,フォトニックネットワークを支える光スイッチ技術,シンポジウム)
- BCS-1-4 高速光スイッチのネットワークへの応用技術(BCS-1.フォトニックネットワークを支える光スイッチ技術,シンポジウム)
- 上流優先スイッチングと分散公平性制御を用いた光バースト交換リングネットワーク