大規模ネットワークの運用・管理のための分散アルゴリズムの研究

点击翻译按钮获取中文摘要

本研究では,大規模ネットワークの運用・管理に注目し,大規模ネットワークの運用・管理のための分散アルゴリズムを開発することを目的として,研究を行った。本年度に得られた主な成果を以下にまとめる。1.ネットワークの最小生成木を求める自己安定分散アルゴリズムの開発:ネットワーク管理の基本的問題の一つである最小生成木構成問題に対し,与えられた分散システムの通信グラフ上において最小生成木を求める自己安定分散アルゴリズムを提案した。提案アルゴリズムは部分木にリンクを追加することで生成木を構成する手続きと,部分木のリンクを交換して最小生成木を構成する手続きからなり,これら2つの手続きを並行して実行することでネットワークの最小生成木が構成される。提案アルゴリズムは自己安定アルゴリズムであり,ネットワークの初期状態や一時故障の有無と無関係に,最小生成木を求めることができる。また,提案アルゴリズムの正当性を証明するとともに,アルゴリズムのメッセージ複雑度についても示した。2.分散アルゴリズムシミュレータの開発:分散アルゴリズムを実験的に評価するための高速分散アルゴリズムシミュレータを開発した。開発したシミュレータにおいては,シミュレーションの対象となる分散アルゴリズムをシミュレータに実行コードの一部に組み込んで直接実行するコンパイラ方式を採用した。また,シミュレータはマルチプロセッサシステム上で動作し,分散アルゴリズムのシミュレーションを並列処理で行う。これにより,分散アルゴリズムの高速シミュレーションが可能になり,大規模ネットワーク上での分散アルゴリズムの動作の詳細な実験的評価が可能になった。