電子情報通信学会ソサイエティ大会講演要旨
B-7-7
ファイルサイズ可変により生じるファイル配送スケジューリングの複雑性
◎赤岡 武(東工大)・菅原真司(千葉工大)・山岡克式(東工大)
キャッシュ技術を用いて,ファイルをネットワーク上に複製配置し負荷分散を行う,様々なファイル配送システムをモデル化したホップバイホップファイル配送において,ファイルのリクエストを送信してから,完全に受信するまでの時間の低減を目的とした,局所最適ファイル配送スケジューリング方式が,1リンクモデルにおいて提案されている.これに対し筆者らは,ファイルサイズ同一とした2リンクモデルにおいて,最適なファイル配送スケジューリングを提案するとともに,中間ノードにおけるファイル配送順序の変更は,実用上考慮する必要が無いことを述べてきた.
本稿では,上記最適ファイルスケジューリングが,ファイルサイズ可変の場合はNP完全であることを述べる.