ファイルネットワークのダイレクトメール型最小費用スケジューリングに関する研究

ファイル転送ネットワークでの「ファイル」とは情報伝送媒体の抽象的単位である.伝送すべき情報は全て1個のファイルに書き込まれ,情報の発信局からネットワークを通して,その情報を必要とする局へそれぞれの必要な部数が,途中の局で必要に応じてコピーされ,伝送されるものとする.そのネットワークの各局には,局固有のファイル当たりのコピー料,コピーできる最大部数,コピーに要する時間並びにそのファイルの必要部数が指定され,局間を結ぶ各回線にはファイル当たりの転送料が指定されているものとする.ダイレクトメール型最小費用転送スケジューリングとは,そのようなネットワークのもとで,ファイルをどの局でどれだけコピーし,どのようなルートで伝送すれば,総費用が最小となるかについて決定するものである.本年度の本研究の主な目的は1.より実用的なファイル転送ネットワークを考察対象とし,スケジューリングのアルゴリズムの実際的な開発の立場から,この課題をさらに詳細に詰める.2.ネットワーク上で異なる種類のファイルが転送される場合に対して,スケジューリングのアルゴリズムを開発する.であった.その結果得られた成果はそれぞれ次のようである.1.転送コストが2段階ならば,極めて簡単な構造でもNP困難になり,最小費用のスケジューリングが容易にはできないことが証明できた.2.対象のネットワークが木構造ならば,2種類の異なるファイルを扱う場合に対しても,線形時間で最小費用のスケジューリングができることが証明できた.これら2点を概観すると,本年度は,より実用的なネットワークシステムに対して,最小費用転送スケジューリングの研究が進展したと言える.従って,容易にスケジューリングができない場合に対して,どのような近似アルゴリズムを開発し,計算機上に実装して,その精度を評価するかが今後の課題となる.

ファイル転送ネットワークでの「ファイル」とは情報伝送媒体の抽象的単位である.伝送すべき情報は全て1個のファイルに書き込まれ,情報の発信局からネットワークを通して,その情報を必要とする局へそれぞれの必要な部数が,途中の局で必要に応じてコピーされ,伝送されるものとする.そのネットワークの各局には,局固有のファイル当たりのコピー料,コピーできる最大部数,コピーに要する時間並びにそのファイルの必要部数が指定され,局間を結ぶ各回線にはファイル当たりの転送料が指定されているものとする.ダイレクトメール型最小費用転送スケジューリングとは,そのようなネットワークのもとで,ファイルをどの局でどれだけコピーし,どのようなルートで伝送すれば,総費用が最小となるかについて決定するものである.本年度の本研究の主な目的は1.より実用的なファイル転送ネットワークを考察対象とし,スケジューリングのアルゴリズムの実際的な開発の立場から,この課題をさらに詳細に詰める.2.ネットワーク上で異なる種類のファイルが転送される場合に対して,スケジューリングのアルゴリズムを開発する.であった.その結果得られた成果はそれぞれ次のようである.1.転送コストが2段階ならば,極めて簡単な構造でもNP困難になり,最小費用のスケジューリングが容易にはできないことが証明できた.2.対象のネットワークが木構造ならば,2種類の異なるファイルを扱う場合に対しても,線形時間で最小費用のスケジューリングができることが証明できた.これら2点を概観すると,本年度は,より実用的なネットワークシステムに対して,最小費用転送スケジューリングの研究が進展したと言える.従って,容易にスケジューリングができない場合に対して,どのような近似アルゴリズムを開発し,計算機上に実装して,その精度を評価するかが今後の課題となる.