マルチチャネルネットワークにおける通信時間予測の複雑さ

松本 裕  ワグナー キエパ クニア  山下 雅史  阿江 忠  

誌名
電子情報通信学会論文誌 D   Vol.J70-D   No.8   pp.1462-1468
発行日: 1987/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(570.1KB)>>
論文を購入




あらまし: 
マルチチャネル化されたネットワークでは,複数のチャネルを用いて,複数のメッセージを同時に伝送することが可能である.本論文では,メッセージの伝送要求発生から伝送完了までの時間を伝送遅延時間と定義し,マルチチャネルネットワークにおける,伝送遅延時間の最大値予測の計算複雑さを議論する.ネットワークにおけるメッセージの伝送は,チャネル組と呼ばれるチャネルの集合を同時に用いて行われる.メッセージの伝送に際して,一つもしくは複数のチャネル組の獲得要求が出される.このとき,要求するチャネル組の数の違いにより,計算複雑さにNP困難あるいは多項式の違いが生じることを示す.