ダイクストラ法による最短経路での複数リンク切断時の最短経路導出法
スポンサーリンク
概要
- 論文の詳細を見る
通信ネットワークにおいてあるノードから他のノードへデータを送る場合, この間の通信コストが最小となる経路が選択される.この経路を求めるために最短経路導出アルゴリズムを用いるが, これらはネットワーク内の接続状態は不変であると仮定していた.これを改善するため, 既にダイクストラ法によって最短経路が求められている状況において, ある一本のリンクが切断されたときを想定し, 最小限の再計算をするだけで最短経路を求めるアルゴリズムが提案されている.本論文ではこれを拡張し, 任意の数のリンクが切断されたときの最短経路導出アルゴリズムを提案する.そして, 本方式による計算量がダイクストラ法による処理に要する計算量よりも大きくならない事を示す.
- 2000-09-11
著者
関連論文
- B-16-23 優先度を考慮した明示的輻輳通知方式のネットワークプロセッサへの実装とその評価
- 筑波大学キャンパスネットワークの歩み
- コンピュータ・ネットワークにおけるNCPの設計に関する-考察
- 動的帯域決定方式を用いたCBQのネットワークプロセッサへの実装方法の検討とその評価
- 動的帯域決定方式を用いたCBQのネットワークプロセッサへの実装方法の検討とその評価
- ダイクストラ法による最短経路での複数リンク切断時の最短経路導出法
- 境界ルータを用いたMobile IPの経路最適化に関する研究
- 境界ルータを用いたMobile IPの経路最適化に関する研究
- 1R-1 境界ルータでのトンネリングを用いたMobile IPの経路最適化に関する研究
- Delay,Throughput,Fairnessのバランスを考慮にいれたネットワークSharing Schemeの評価基準の提案
- マイクロモビリティ情報に基づいた動的帯域予約法と呼受付制御方式の提案(移動通信ワークショップ : 次世代ブロードバンド無線通信の実現に向けて)
- マイクロモビリティ情報に基づいた動的帯域予約法と呼受付制御方式の提案(移動通信ワークショップ : 次世代ブロードバンド無線通信の実現に向けて)
- マイクロモビリティ情報に基づいた動的帯域予約法と呼受付制御方式の提案(移動通信ワークショップ : 次世代ブロードバンド無線通信の実現に向けて)
- マイクロモビリティ情報に基づいた動的帯域予約法と呼受付制御方式の提案(移動通信ワークショップ「次世代ブロードバンド無線通信の実現に向けて」)
- Mobile IPにおけるセル間移動時の通信の瞬断を防ぐ経路切りかえ方式の提案
- 再帰プロセスのための等価性判定およびエラー検出アルゴリズム
- 再帰プロセスのための等価性判定およびエラー検出アルゴリズム
- 再帰プロセスのための等価性判定およびエラー検出アルゴリズム
- LOTOS言語教育支援環境のためのプロセスの誤り検出法
- MSCからのプロセス合成(アルゴリズムと計算量理論)
- Extension of Synthesis Algorithm of Recursive Processes to $\mu$-calculus
- Inductive Synthesis of Recursive Processes from Logical Properties
- μ-calculusによる再帰プロセスの合成
- プロセス合成のための支援環境に関する研究
- μ-calculusによる再帰プロセスの合成
- プロセス合成のための支援環境に関する研究
- プロセス合成のための支援環境とその試作
- μ-calclusによる再帰プロセスの合成アルゴリズム
- 汎用並行プロセス計算システムの設計開発
- プロセスの枚挙に基づいた代表的プロセスの合成
- 様相論理式による基本プロセスの合成アルゴリズム
- バイパスとループバック機能を持つ2重リングの信頼性
- RSIPサーバにおけるポート番号によるパケットフィルタリングの提案とその性能検証(ネットワークセキュリティ)(ブロードバンドネットワークサービス)
- DNSフィルタ方式によるミラーサーバ選択法の提案と実装(高速ネットワークとマルチメディアアプリケーション)
- B-16-7 ゲートウェイのための Host Information Protocol のネットワークプロセッサへの実装
- Cellular IP 環境におけるページングキャシュタイムアウト時間に関する一考察
- 各端末からの要求を考慮したマルチキャスト通信のためのリソース予約スタイルの提案
- Cellular IP 環境におけるページングキャシュタイムアウト時間に関する一考察
- 各端末からの要求を考慮したマルチキャスト通信のためのリソース予約スタイルの提案
- TCP Renoの早期再送時における帯域制御の動的変更方式の提案(:フォトニックネットワーク, IP over WDM技術, 及び一般)
- 無線LANにおけるCBQの優先度割当て方式の提案
- 無線LANにおけるCBQの優先度割当て方式の提案
- 無線LANにおけるCBQの優先度割当て方式の提案
- CBQによる使用帯域制限の動的決定方式
- ATM LANにおけるリンク情報の通知を用いた重み付き動的帯域予約方式の提案
- 明示的ワイヤレスリンクロス通知を用いたTCPにおける輻輳制御方式の一考察
- ATM LANにおけるリンク情報の通知を用いた重み付き動的帯域予約方式の提案
- 明示的ワイヤレスリンクロス通知を用いたTCPにおける輻輳制御方式の一考察
- 高速LAN通信システムの平均応答時間の近似評価
- マルチアクセス通信のためのグループ化2次元ラウンドロビンスケジューラの提案
- キュー長を考慮したEarly Packet Discardの改良
- キュー長を考慮したEarly Packet Discardの改良
- ディファレンシャルサービスに基づいた伝送遅延に関する明示的輻輳通知方式の提案
- デイファレンシャルサービスに基づいた伝送遅延に関する明示的輻輳通知方式の提案
- ディファレンシャルサービスに基づいた伝送遅延に関する明示的輻輳通知方式の提案
- 優先順位を利用した輻輳制御に関する考察
- 分散型電子メールアドレス検索システム
- 分散型電子メール宛先情報探索における平均探索長の評価
- 電子メール宛先情報提供サービスシステムの開発
- バイパス機能をもつ多重多段リングシステムの信頼性
- Host Information Protocol に関する研究
- ホモジニアスなリアルタイム通信システムの上限付き平均応答時間とトラヒック
- LAN通信システムのポイント・トゥ・ポイント平均応答時間の近似解析
- 一リンク形LANのシミュレーションによる解析
- ハイブリット型バンヤンネットワークのパフォーマンス解析
- バイパスをもつ改良バンヤン網構成に関する評価
- 異なるCPU処理能力を持つリアルタイム通信システムの平均応答時間と入力トラヒック
- パケットの優先度を考慮したグループ化2DRRスケジューラの改良
- Host Information Protocol に関する研究
- バッファと2入力1出力スイッチによるクロスバスイッチ構成法の提案
- サーバ証明書の有効性を確認するSSL/TLS通信プロトコルの改良とその評価
- 5N-7 SSLによる暗号化通信のための公開鍵の変更を考慮した時限付き証明書に関する研究