第 1 章 参考文献
2.2 システムモデル
まず,図2.1に二つのSpeedup Factorを用いた入出力バッファ型交換機を示す. こ のモデルにおいて,セルの到着,及び転送はベルヌーイ過程に従い同期的に処理され
第 2章 二つのSpeedup Factorを用いた入出力バッファ型ATM交換機 31
N 1 2 S C1 , C2
1 2 S
1
C1 , C2 Bo Bo Head-of-line
2 1
1 1
N 2
Bi
Bi
図 2.1: 二つのSpeedup Factorを用いたN ×N入出力バッファ型ATM交換機
るスロットモデルとする. システムの単位時間をタイムスロットと呼ぶ. 入力バッ ファは比較的簡単な回路構成で実現できるため[2],入力バッファサイズBiは無限長 とし, 回路構成が複雑なため増設が困難な出力バッファサイズBoは有限長とする.
また,入力ポートへのセルの到着率は時間によらず一定であり,出力先アドレスの与 え方はランダムである均一トラヒックを扱うものとする.
2.2.1 入力側の動作
交換機の入力側に到着したセルは, 入力バッファへ入力される. 入力バッファサイ ズは無限長であると仮定しているので, 入力バッファでのオーバーフローによるセ ルの棄却は起こらない. 入力側処理装置のHead of the Line(HOL)に入力されたセ ルは, N 個ある出力ポートの中の1つを確率1/Nでランダムに選び転送される. こ こで,複数のセルがある一つの出力ポートを目指す競合時には, 最大Speedup Factor C1またはC2(C1 > C2)個までのセルが転送を許される. 一方, 競合に敗れたセルは HOLから退去することはなく, 競合に勝ち, 出力側へ転送されるまでHOLで待機 する.
第 2章 二つのSpeedup Factorを用いた入出力バッファ型ATM交換機 32
Case 1(Output Queue Length at previous time slot ≦ S) 4
Go Go
Go
Go
C1
S
Loss
slot i-1
slot i
Go Wait
Wait
S 2
Go
C2
slot i-1
slot i
Case 2(Output Queue Length at previous time slot > S)
図 2.2: 出力側において、二つのSpeedup FactorC1, C2(C1 > C2)が適用される様子
2.2.2 出力側の動作
図2.2に出力側において, 二つのSpeedup Factor C1, C2(C1 > C2)が適用される様 子を示す. 提案モデルは, 出力待ち行列長にしきい値S を設け, 1タイムスロット前 の出力待ち行列長がSを越えていなければC1 を適用し(Case 1), 越えていればC2
を適用する(Case 2). 出力バッファサイズがBo = 5, 出力待ち行列長のしきい値が S= 3である時に, タイムスロットiにおいて4個のセルがこの出力を目指している 時, 2つのSpeedup Factor C1, C2(C1 > C2)が適用される場合を図において考える.
上図はタイムスロットi−1における出力待ち行列長が3であるので, 待ち行列長は Sを越えておらず, C1 = 4が適用される. 従って, タイムスロットiにおいて4個の セルが出力バッファに転送される. ここで出力バッファより1個のセルが処理され るので出力待ち行列長は2となり, 出力バッファには空きが3つしかないため, ラン ダムに選ばれた3個のセルが出力バッファに入力され,残りの1個のセルは棄却され る. 下図は, タイムスロットi−1における出力待ち行列長が4であり, Sを越えて
第 2章 二つのSpeedup Factorを用いた入出力バッファ型ATM交換機 33 いるため, C2が適用され2個のセルがランダムに選ばれ出力バッファに転送される.
残った2個のセルは各入力ポートのHOLで1タイムスロット待機した後,タイムス ロットi+ 1で再び競合に参加する. 競合に勝った2個のセルは, 出力バッファに転 送される. ここでC1 =C2 と設定すると従来モデルと一致したモデルとなる．提案 方式は，出力待ち行列長がスレッショルドを越えているかの2値情報を入力側に伝 え，その値によって入力側で待機させるセル数を制御する．このように出力側の情 報を用いて入力側を制御する機構は広く用いられており，容易に実現できる．
本論文では，出力バッファに入力できないセルは棄却される．しかし，出力バッ ファに入力できないセルを入力バッファにて待機させることは容易である．競合に 敗れ，出力バッファに入力できないセルの扱いに関しては，下記の改良案が考えら れる．
(1) 競合に勝つまで，入力バッファで待機
(2) 競合回数が一定回数に達するまで，入力バッファで待機 (3) 競合に敗れた場合，一定確率で入力バッファで待機
(1)の方式では，出力バッファにおけるセル棄却の発生を完全に防ぐことができる．
しかし，入力バッファにFIFOを用いた場合，HOLブロッキングにより，入力バッ ファでの遅延が大きくなる．従って，この方式を採用する場合，入力バッファにHOL ブロッキングによる影響を軽減する対策が必要になると考えられる．例えば，RIRO
(Random In Random Out)を用いることや，入力バッファの先頭以降からのキュー
出力を可能にするwindow方式，さらには，出力ポートごとに入力キューを分ける といった対策が挙げられる．(2)の方法では，競合回数が一定回数に達するまで，入 力バッファでセルを待機させることで，出力バッファで生じるセル棄却を大幅に軽 減できると考えられる．これに加えて，競合に敗れる回数が一定回数に達した場合 はセル棄却を施すことにより，入力バッファでの遅延特性の劣化を軽減できること が見込まれる．(3)の方法では，入力バッファでのHOLに存在するセルの競合回数
第 2章 二つのSpeedup Factorを用いた入出力バッファ型ATM交換機 34 を記憶しておく必要がなく，実装面は比較的容易であり，(2)の方法と同様の効果が 期待される．このように，現実的には色々な改良案が考えられるが，本論文におい ては，システムモデルを単純化し，最も基本的な構成である出力バッファにセルが 入力できない場合は棄却するというモデルについて性能解析を行う．