解析手法

本研究ではpermutation capabilityを通信遅延として評価する．N×N光学オメガ 網においてpermutation capabilityを解析的に求めるため，ネットワークの各ス テージのスイッチを通るパスの最大数に注目する．各ステージのスイッチは２入 力２出力で構成されているため，各ステージのスイッチを通るパスの最大数を求 めるために以下の手法が適応できる．

1. あるステージ $m(0<m\le \lceil \frac{\log_2 N}{2} \rceil)$の各スイ ッチに入るパスの最大数を求めるために，前のステージ$m-1$の各スイッ チに入るパスの最大数×２を行う．
2. 再帰的にステップ１をくり返し，ステージ０まで行う．

ステージ０において各スイッチを通るパスの最大数は２であるので上記の１，２ においてステージ$m$のスイッチを通るパスの最大数$2^m$が求められる．光学オ メガ網においてpermutationを実現するために１つの入力に対してそれぞれ１つ の出力が対応しているので，中央ステージ $\lceil \frac{\log_2 N}{2} \rceil$ で各スイッチを通るパスが最大になり，最終ステージ $\log_1 N-1$において各ス イッチを通るパスの最大数が２になることがわかる．

以上より中央ステージにおいて各スイッチを通るパスの最大数は $2^\lceil \frac{\log_2 N}{2} \rceil$である．ネットワーク内の他のスイッチ に対してこの値より大きいパスは通らないことを保証するため，任意の permutationを実現するためのサイクル数の上界つまりpermutation capability と自然に同一視できる．

図 6: N×N光学オメガ網におけるステージ別パスの最大数