permutation capability

光学多段相互結合網のスイッチは同時に２つ以上の情報を処理できないため，１ つのスイッチに同時に２つの情報が入力されることを禁じている．１つのスイッ チに同時に２つ以上の情報が入力されることをコンフリクトと言い，図４に光学 オメガ網におけるコンフリクトの例を示す．

コンフリクトを防ぐためにpermutationに対してサイクルを分けて送る必要があ る．permutation capabilityとは任意のpermutationにおいて必要なサイクル数 の上界とする．また本研究においてpermutation capabilityを通信遅延として評 価する．図５は８×８光学光学オメガ網においてステージ１のスイッチ１０を通 る４つのパスの例を示しており$y_0$，$y_2$，$y_4$，$y_6$がどんな値をとって も４サイクル以上になることはなくpermutation capabilityは４であることを示 している．

図 4: 光学オメガ網におけるコンフリクトの例

図 5: ８×８光学オメガ網におけるpermutation capability=4の例