4J-4

情報処理学会第66回全国大会

折り返し型自律優先キューイング機構における順序補償方式の一考察
林秀樹†

岩田誠†,‡

浩詔‡

寺田

通信・放送機構†

Homeward stages

Outward stages
Lowpriority

A Study of A Correcting Order Method in the Autonomous
Priority-Based Queueing Scheme Utilizing A Folded Pipeline†Hideki Hayashi †,‡Makoto Iwata ‡Hiroaki Terada,†,‡Kazunori Shimamura†Telecommunications Advancement Organization of Japan‡Kochi University of Technology

和典†,‡

高知工科大学‡

１．はじめにネットワークの進展に伴い，様々なサービスやアプリケーションの導入が進められ，これらに適切な品質を提供するための QoS 技術が必要とされてきている．これまでに，多くの QoS に関する研究が行われてきたが，ほとんどが複雑な処理機構を必要とし，実装上の課題が残されている．
筆者らは，柔軟かつ簡易に QoS 制御が実現できる，自己タイミング型パイプライン STP の折り返し構成による自律優先キューイング機構を提案し[1]，その基本 LSI 回路の試作を行っている[2]．また，本機構がスケジューリング機構を用いずとも，キューイング遅延やパケット廃棄の差別化を原理的に柔軟に行えることを示した[3]．
本稿では，さらに，本機構の自律動作に伴った出力の順序逆転の可能性を解消する，順序補償方式について議論し，この方式を適用した場合の評価結果を示す．
２．自律優先キューイング機構
STP 内では，各パイプライン段（ステージ）のパケットの保持／移動が，その前方段に別のパケットが保持されているか否かで決まる．このため，隣接するステージ間のみに必要な制御が局所化され，大規模かつ柔軟な構成を容易に実現できる．これらの特性を応用した，STP による優先キューイング制御方式の基本構成を図 1に示す．
このキューイング機構では，パケットは原則バイパスを試み，移動先が競合した場合，その優先度（クラス）に応じて，バイパスの可否が決まる．この局所動作の繰り返しの結果，高優先度のパケットは早く送出され，低優先度のパケットは徐々にキューイングされる．

島村Highpriority
Input:Forwarding route:Queue I/O

Output:Bypass route:Pipeline stage

図１．自律優先キューイング機構の基本構成
ただし，この局所的な自律動作は，同一クラスであっても，先に入力されたパケットがキューイングされ，後に入力されたパケットが先に送出され，出力時に順序逆転するリスクを伴う．
３．順序補償方式
3.1 基本動作（１）往路側ステージにおける動作・シーケンス番号（SN）の付与
キュー入力時，クラス別に SN がパケットに付与される．
・バイパスフラグ（BF）
パケットは，クラス別メモリ CBM に記録された同一クラスの SN と自身の SN を比較し，差分が 1 の時，バイパス可とするフラグ BF を有効にする（図 2(a)）．BF の無効なパケットは，バイパスしない（図 2(b)）．
・バイパス
BF の有効なパケットは，バイパス先が競合しないか，競合パケットが自身の優先度未満であればバイパスする．

3−301

Class-based memory
AB
C000
Discard flagx

Enablebypass2y700

Sequential
number600

Latency(Normalized)

B2

B3

800

k=1 (Ordered)k=0 (Not ordered)k=0 (Ordered)

400

A0

B0C0

Discard flag

x1y

Sequential
numberDisablebypassk=2 (Ordered)k=1 (Not ordered)500

3-2 = 1B3

k=2 (Not ordered)

300
200

3 -1 ≠ 1

10000(a) A case of enable bypass flag

Cy
DisablebypassB3x1y

Sequential
number3 -1 ≠ 1A0B0

C0x1y‑10.2

0.3

0.4
0.5
0.6
Output blocking rate

0.7

0.80.91

図３．遅延特性に対する順序補償の効果

Class-based memory
ABC
Discard flag
000

B30.1

Discard flag
Sequential
numberDisablebypass(b) A case of disable bypass flag

図２．バイパスの可否判定（２）復路側ステージにおける動作
・クラス別メモリ（CBM）
通過パケットの SN をクラス別に記録する．
3.2 廃棄時の動作（１）往路側ステージにおける動作
・廃棄フラグ（DF）
パケットの廃棄時には，その SN を CBM に記録し，そのクラスの DF を 1（有効）にする．
（２）復路側ステージにおける動作
・ピギーバック
ステージ通過するパケットは，3.1（２）の動作とともに，DF が有効な CBM の SN とそのDF を ピ ギ ー バ ッ ク し ， 移 動 先 ス テ ー ジ のCBM に，その情報を写す．ピギーバックされた CBM の DF は 0（無効）に戻す．
これらの制御方式により，パケットの自律動作に拘らず，導通フローの順序補償が可能となる．この制御方式の機能は，STP の各ステージが分散された機能部を利用し，容易に実装ができる．
４．評価
この順序補償方式の適用の有無による，特性の違いを比較評価した．図 3 は，本キューイング方式の基本構成において，遅延特性を比較評価したものである．ここでは，入力トラフィッ
クを，k = 0,1,2（値が大きいほど低遅延かつ高廃棄率）の 3 種の優先度のクラスが，ランダムに構成された最小サイズのパケットの連続投入とし，キューイング機構が過負荷状態に達し，一定時間経過するまで入力し続けて評価した．
評価結果から，順序補償が遅延の大きなクラスの遅延低減に効果があり，高輻輳時に遅延の大きなクラスの遅延が一方的に増加する問題について，改善効果があることが分かる．これは，順序補償がパケット個々の離散的振る舞いを抑制し，キューイング時の動作が均質化することから，遅延変動が縮小し，平均遅延が低減するためと考えられる．
５．まとめ
本順序補償方式は，優先クラスごとの先入れ先出しキューイングを保持でき，キューイング機構内のパケットの滞留時間を均質化できる．
この特質が，特に高輻輳時の遅延の差別化に効果を与えることが分かった．
今回の評価では，本キューイング方式の最も基本的な構成において，過負荷時の順序補償の効果を確認した．本キューイング方式は，各ステージの機能部を活用し，様々な遅延制御や廃棄制御を行え，これらの機能の活用により，さらに性能改善が期待できる．今後の課題として，順序補償時にこれらの制御機能を活用した場合の評価や，この順序補償方式の，TCP/IP フローとの親和性についての評価が挙げられる．
参考文献[1] H. Hayashi, M. Iwata, and H. Terada, “AnAutonomous Class-Based QoS Control Utilizing A
Self-Timed Folded Pipeline,” 4th Int. Conf. on
Advanced Comm. Tech., pp.469-474, 2002.
[2] M. Iwata, M. Ogura, Y. Ohishi, H. Hayashi, and H.
Terada, “100Mpps Fully Self-Timed Priority
Queue: FQ,” 2004ISSCC, 2004.
[3]林, 岩田, 寺田, “クラス別 QoS 制御向き自己同期型優先キューの性能評価,” FIT2003 情報技術
レターズ, vol.2, pp.313-314, 2003.

3−302