パケット処理装置に適したトークン方式バス調停法と 性能解析

長野工業高等専門学校紀要 ･第

号

パケ ッ ト処理装置 に適 した トークン方式バス調停法 と 性能解析

和崎克己 不破泰 中村八束 清水英孝

( 平成

年

月

The Reallization and Evaluation of 

A   B u s   A r b i t r a t i o n   M e t h o d   B a s e d   o n   T o k e n   P a s s i n g   Suited for Packet Processing Devices

Katsumi WASAKI Yasushi FUWA Yatsuka NAKAMURA and Hidetaka SHIMIZU

Intllispaper,weproposeanewbusarbitrationmethodsuitedforcomposingPrOCeS‑ sorsforpacketexchange.Arbitrationarc㌔hitectureprovidesonesignallineforconnecting theprocessorsOfeacllperipheralchannelinarlngandcirculatesa1‑bittokenamong tllem.Also,WeconsiderdividingthechallnelSintomultiplegrollpSandproposeanin‑

dependentbuscompositionmethoddesignedtore血 cethepacketwaitingtimes.The characteristicsoftlleProposedmethodareexaminedbyconstructingandanalyzinga Markovianmodelofthesystem.Finally,weveri丘edtheaccllraCyOfanalysisbycompar‑ 1ngtheresultsagainstsimula.tionandusetheseresultsindiscussingthebestdivisions ofchannelsintermsofpacketdelay.

1 まえがき

コンピュータネットワークにおけるター ミナルサーバ等のパケ ット処理装置においては, 装置内の各モジュール間でパケットを転送するためのバスの構成 と,その調停法が大切で ある.特 に最近の

技術の進歩に伴い, パケット処理装置において もマルチプロセ ッサ 化によ り処理能力の向上が図 られてお り, バスの構成 ･調停の重要度はますます増大 してい る.従来 よ り,バスの調停 に関する多 くの研究が行われ,またバス調停機能を備 えたい くつ かの標準バス も規格化 されている ( 例えば,文献 1 ) 〜6) ).

■平成

年

月7 日 電子情報通倍学会借越支部大会発表予稿に加翠 ' ●電子制御工学科 助手

… 僧州大学工学部情報工学科 助教授

… ●僧州大学工学部情報工学科 教授

… ̀ ●長野県情報技術試験場 研究月

64

図

の構造 図

Fig･1:ConfigurationofS‑net･ Fig･2:Configurationofaterminalserver･

著者 らは,これまで

とよぷキャンパスネ ットワークを提案 し, 構築 ･連用 を行 っ て きた.

は,リング型に接続 したター ミナルサーバが端末か らのパケットを

台の中 央交換装置に集め,この装置か ら各端末にパケ ットを送僧するというスター型の論理構成を とる ( 図

参照) .このター ミナルサーバは, 端末を接続する複数の周辺チャンネル毎のプロ セ ッサ と,リングに接続する 1つのホス トチャンネル用のプロセッサがバスを共有 している＼

( 図

参照) .パケ ット化 された端末からの受倍データが, バスを通 してホス トチャンネルに 出力 される.つ ま り,複数の周辺チャンネル間で,ホス トチャンネルへのバスを調停 し合い なが ら利用する構成をとる.

本論文では,この ような構成のシステムに適 したバス構成 ･調停法 を提案する.このシ ステム構成は, 周辺チャンネルをプ ロセ ッサシステム,ホス トチャンネルを共有の メモ リや

Ⅰ/

0チャンネル と置 き換 えれば, 通常のマルチプロセ ッサシステムの構成 と同 じであ り, 提 案手法は汎用性が高い.その原理は, 各周辺チ ャンネル間をリング状 に結ぶバスとは独立 し た 1本の倍号線 を用い,バスの調停 をこの倍号線 を流れる

の トークンを用いて行 うと い うものである.トークンパ ッシング方式を用いたネットワーク調停法は

等 で規定 されている.また,データを送倍すると同時に トークンを次のノードに手渡す とい う 本論文で示す方法

で後述)についても

等のマルチ トークン方式 とし て

DDI物理層 に規定 ･応用 されている.提案方式はバス調停に伴 うオーバヘ ッドを小 さ くするため,プ ロセ ッサ毎に

を用意 し,状態セ ット用の

本の倍号線で リング 状 に接続する.結果,トークン転送が高速で高いバス ･スループ ットが得 られる,バス使用 権は各プロセ ッサ間で均等 に与えられる,使用する倍号線が少な く調停用ハードウェアの規 模が小 さい, 等の利点を享受で きる.更 に周辺チャンネルの数が増 えた ときには,周辺チャ

ンネルを複数のグループに分割 し独立 したバス構成にすることで, パケット待ち時間の減少

を図る構成について も提案する.

バ ケ ッ ト処理装置に適 した ト‑

ン方式, :ス調停法 と性能解析

本方式の特性を議論するために, マルコフモデルを用いた数学モデルを作成 して性能解析 を行 う.解析 には平衡点解析

とよぶ手法を用い,解析精度を検証するためにシ ミュレー ション結果 との比較を行 う.また, 解析結果を用いて周辺チャンネルの最適なグループ分け について も論 じる.

2 バス調停方式

2‑1

トー クン リングに よるバス調停

提案するバス調停のシステム構成 を図

調停方法を以下に説明する.

cho‑ ChM̲ 1 の

チャンネルそれぞれにプロセッサ CPUco〜CPUcM̲1が用意され, 専用の共有バスによって,ホス トプロセ ッサ CPUHへパケットを直接転送する.また,トー

クンリング

と呼ぶ

本の倍号線で

台のプロセッサを次々とリング状に接 続する.バス使用権の調停は,この トークンリング上を循環する

の トークン

を 用いて行 う.トークンを獲得 したプロセッサが, バスの使用権 を有 している.プロセ ッサ間

を循環する トークンは, 共有バス とは独立 して転送される.

RSnip‑flopによる トークン循環の構成図を図4に挙げ,バス使用権の調停方法について,

説明する.

この構成は,プロセ ッサ毎に

状態セ ット用の 1本の倍号線で リン グ状 に接続するものである.

人力 S, Rと出力

を有する.入力

または

に状態変化のためのパルスを送ることにより,状態侶 ( 出力

は各々

または

にセットさ れる.あるチャンネルにトークンが到着する ( そのチャンネルの

にパルス が入る)と' , 状態借が 1にセ ットされる.この時,当該チャンネルのプロセ ッサは,バスの使 用権 を獲得 し,バ ッファに送出すべ きパケットを保有 しているならばバスを使用 して,バ ッ

ファ内のパケットを一つ送る.

送出すべ きバケットを保有 していないか,または

つのパケット送倍が完了 した後,トー クンを次のチャンネルへ渡 し, 使用権 を放棄する.これは, 次のチャンネルに設けられた

と,自身の

の人力

にパルスを送ることに対応する.以上の 作業を各プロセッサが次々と行 うことにより,トークンの循環によるバス使用権の調停が行 われる.

本方式の特徴 を以下に述べる.トークンの転送のためには,RSf

^にパル

スを与えるのみという,簡単な方式を採用 したため, 次の周辺チャンネルへの トークン転送

が高速に行われる.このため, バス調停のためのオーバーヘッドが小さくて済む.よって,高

いバスのスループ ットが得 られる.また,トークンリング上の各チャンネルは トークンの獲

得に閑 し互いに対等であ り,バス使用権は各チャンネル間で均等に与えられる.更に本方式

は 1本の倍号線でチャンネルを次々に接続 してい く方法であ り,使用する倍号線が少な く,

また必要なハードウェア規模 も小さ くて済む.

66

和崎克己 ･不破 泰 ･中村八束 ･清水英孝

図

図

による トークン循環

2‑2 バスの分割

提案 したバス調停方式では, バ ッファにパケットを有 して出力 を待っているチャンネルへ, 循環 している トークンが到達するまでの時間は, 周辺チャンネル数 〟 が増 えるに従 って増 大する.提案方式では,トークンが当該チャンネルへ到達するまでの時間が短いほ ど,受倍 バ ッファに格納 されているパケットの待ち時間が小 さい.このため

トークンリングあた りのチ ャンネル数を減 らし, パケットの待 ち時間を小 さくする方策 として,周辺チ ャンネル を複数のグループに分けて,独立 したバス とする構成を提案する.階層化 した トー クンリン グによるバス分割の構成を図

に挙げ,調停方法を以下に説明する.

M 台の周辺チャンネルを

台ずつ

台のプロセ ッサ

)間でローカルバス

を調停 して用い, パ ケ ットをローカルプロセ ッサ

に転送する

台のローカルプロ セ ッサは, 共有するバス

を調停 して用い,受倍 したパケットをホス トプロセッ サへ転送する.各グループ内プロセ ッサお よびローカルプロセ ッサ間のバス調停は,各々前 節で述べた

を用いた

の トークンリングによる方法である.

また,各グループ内の

と,上位の

の転送速度は同じである.こ のため,ローカルプロセ ッサは,下位の

から転送されるパケ ットを受僧 し始め ると同時に

を用いてホス トプロセッサへのパケ ットの転送が可能である.

このバスの分割による効果は

で考察する.

′ {ケ ット処理装置に適 した トークン方式バス調停法 と性能解析

図

階層化 トークンリングによるバスの分割

3 特性解析

本章では, 提案方式の特性 を議論するために,マルコフモデルを用いた数学モデルを作成 して性能解析 を行 う.

最初に図

に示す トークンリング上の各周辺チャンネルの各々が とり得る状態をモード として表 し,このモード間の遷移の関係を表現 した離散マルコフモデルを作成する.次に, 作成 したモデルを平衡点解析

の手法で解析する.更に, バスを分割した方式について も, 特性解析の検討を行 う.

3‑1

仮定

モデル化 と解析 を容易にするため,以下の仮定を行 う.

(Al)

チャンネルが次のチャンネルにトークンを転送するために要する時間をLL とする.L

時間を

ステ ップ とし, 解析はこの Lf 毎の時間単位 ( ステップ)によって行 う.

(A2)バケットの転送に必要な時間をTaとする.時間 Taはトークン転送時間

L i の整数倍 と する.つまり

を満たす整数 Hが存在する.

( A3 ) 各チャンネ) I , 内の受倍バ ッファ容量は有限とし,蓄えられるパケット数を T とする.

68

和崎克己･不破 泰･中村八束･清水英孝

図

トークンリング上のチ ャンネルのマルコフモデル

( A4)各チャンネルでは,送出すべ きパケットが 1ステップ当り確率Uで一つ発生するもの とする.

3‑2

モデル化

故実方式の うち, バスを分割せず全体を

つの トークンリングで調停する場合の離散マル コフモデルを作成する.作成 したモデルを図

に示す.回申,モードを四角で表す.

各モードは,トークンの受倍 を待つか,トー クンを転送中であるモード ( 以下 Ⅳ モード) と,トークンを持 ち,パケ ットを送府中であるモード ( 以下 βモード)とに分かれる.

Ⅳ モードにあるチ ャンネルの状態は,

つのパラメータで決定 される.一つは,そのチ ャ

ンネル内のバ ッファに V個

,

, ‑ ･ , T) のパケットがあるとい うVパ ラメータである.

バ ケ ッ ト処理装置に適 した トークン方式, . 'ス調停法 と性能解析

もうーつは,トークンの流れ と逆の方向に,リング上を xチ ャンネル

,

, ･ ･ ･ , M ‑1 ) さかのぼったチャンネルが,現在 トークンを持 っているとい うTパ ラメータである.Vパラ メータの値が i

パ ラメータの倍が jの

モードを, Wt ･ , 3 . と

く･

∬‑O

の Ⅳ モードにあるチャンネルは,トークンを持っている.このとき,このチャンネル がバ ッファにパケットを持たない場合,次のチャンネルへ トークンの送倍を開始 し , W o, M‑1

モードへ遷移す る. そ して,他のチ ャンネルはすべて ∬パ ラメータの値 を

減 らす.一 方

の Ⅳ モードにあるチャンネルがパケットを持つ場合は ,βモードへ遷移する.

βモードにあるチャンネルの状態は

つのパ ラメータによ り決 まる.一つは, 転送中のパ ケット. を含めてバ ッファ内に y個 ( y

,

, ‑

のパケットを有するとい うyパラメータ である.もう一つは, パケットの送倍を完了するまでに,あとZステップ (

,

, ‑ , H‑1 ) 要するとい うZパ ラメータである

パラメータの億が i

Zパ ラメータの値が jの

モード を

l

･ と普 く･

Z

パラメータの倍は,ステップ時間毎に

減る.この時, W モードにある他のチ ャンネルの xパ ラメータの倍は, Sモー ドにあるこのチャンネルが トークンを保持 しているため,変化 しない.チ ャンネルが

0のモー ドにある時は,パケ ットの送出をすべて完了 してお り, 次の遷移で トークンの転送を開始 して

% ‑ 1 , 〟‑1 モードとなる ( パケット数 も

減る)･ま た

Ⅳ モードにある他のチャンネルは

∬パラメータの値 を

減 らす.

ここで, 確率変数

を定義する

は,

A(n)‑

1

トークンを持つチ ャンネルは, 遷移時に トークンを持 ち続ける

o

トークンを持つチ ャンネルは, 遷移時に トークンを送倍する

( 1)

A(n)‑1

の時は

モードにある他のチャンネルの a . パラメータの値は変化せず

の時は ∬パ ラメータの億が

減 る.

3‑3

解析

3‑3‑1

平衡点方程式

作成 したモデルの解析 を行 う.このモデルにおいて, Wv , Cモードに

るチ ャンネル数を表 す確率変数 を

v , ｡

モー ドにあるチャンネル数 を表す確率変数を

とお く･そ して, モデルの状態ベク トル

を次の ように定義する.

n‑( wo

.

, I , ･ ･

Wo, M ‑

l ,

l , 1 , . ･

Wl , M ‑ 1 , ,WT , 0,WT , 1 , ･ ･

,WT, M ‑1 ,

81 , 0,Sl , I , ･ ･ ･,Sl, H‑1

,

,

, ･ ･ ･,S2, H‑

,ST . 0,ST , i , ･ ･ ･,ST. H‑1)

このベ クト

は,既約な有限状態マルコフ連鎖 となる.このマルコフ連鎖 を, 平衡点解

析の手法を用いて解析する.平衡点解析では,システムは常に平衡点に留 まっていると仮定

70

和崎克己･不破 泰･中村八束 ･清水英孝

する.そこで,各モードへ流入する平均チャンネル数 と各モードから流出する平均チャンネ ル数 とを等 しくおいた次式 を得る.

wi.0

^‑D

o ( i‑0 , 1, ‑ , T‑1)

wT,0

‑CD

wi,i‑丁

二

^{Di wo}

^o

,

, ･ ･ . , T‑1 ) (

^‑1, 2, ･ ･ . , M ‑1 )

,

, ‑ , M ‑1 )

( M ‑1 ) A( n)

St‑IZ=

Sl,I

(M ‑1)

A(

1‑

A( n)

なお,式中 C, Dは次式で定義するものである.

C

‑ ( 1‑Mq) ( 1‑H

D = ( M 11 ) A( n)

C( 1‑A( n) )

wo , o ( i

,

･ , T) ( 7 )

そ して

Oについて解いた式から , A( n)に関する次式が得 られる･

1

^{+ D} ‑ ^{DT .( M ‑}

+a

〈

‑ (1‑

A( n

[ 諾

D ‑D

+

.( M ‑

1‑か ■‑ '〉 ■ 1‑A( n)

与 えられたc r , M , Hか ら,この

を満たす A( n)を求め

< ̲A( n)

,この A( n)と

より平衡点における

の要素がすべて求まる.平衡点解析では,システムは常 に平 衡点 に留 まっていると仮定 し,解析 を行 う.このため,ここで求めた平衡点における要素の 値 を用いて,平均パケ ット遅延 を3‑3‑2に示す様 に求める.

3‑3‑2

平均バケ ット遅延

ター ミナルサーバ内での平均パケット遅延は, 周辺チャンネルでのパケット発生か ら,ホ ス トプロセ ッサへの転送開始 までの,バ ッファでの待ち時間 となる.この待ち時間は,モデ ルの解析 結果 とリトルの公式により,以下の様 に求める.

D l‑

宏 一H

^{( ll )}

バケ ット処理装置に適 した トークン方式バス調停法 と性能解析

なお,

l はシステムが平衡点にあるときバ ッファ内にある全パケット数,また

はバ ッ ファか ら各ステップ時間毎に出力されるパケットの個数であ り,次式で与えられる.

T A(‑I T tI‑1 Nl‑∑

∑ i

∑

^{s , , ,}

t'‑

1 才 ^‑0 y = l I

T

Ql=E

s

y

=1

3‑4

バス分割方式の解析

バスを分割する方式 ( 図

について解析する.下位の周辺チャンネル群 における解析 は

の解析 と同様である.

下位チャンネルが

モードか ら遷移する際,パケットの転送が開始される･よって, 下位 リングか ら転送されて くるパケットの発生確率 qH は, 次式で与えられる.

T

qH

¹

y‑¹

^{竿 業}

^T

与えられた

から,

を満たす

を上位 リングについて求める.上位 リング でのパケット転送待ち時間

ガは,求めた状態ベクトルから(

と同様に求めることがで

きる.従 って,バス分割方式での平均パケット遅延

は次式で与えられる.

D2‑Dl+DH (15)

4 評価

これまでに検討 したモデルによる解析結果の精度を調べるため,シミュレーションによる 結果と比べる.また, 本システムの性脚 こついて論 じる.数値例は, チャンネル数 〟 を

とし,トークンを

,パケット長を

として解析する.共有バスのバス幅は

する.

この条件下で仮定

における

は,

自分の

と,次のチャンネルの

を出すのに要する時間であ り,ポー トへの出力命令一回分の実行時間となる.また,バスへ のパケット送倍は,一皮の出力動作で

送宿 し,この出力動作は上記

f と同 じポー トへ の出力命令の実行時間である.このため, パケット送倍に要する時間 ( Ta)は, ( パケット長÷

8)×Lt

となる.従って

‑

はパケット長÷ 8 の億をとり, パケット長が

のと き ,

シ ミュレーションは仮定

を用い,シミュレーシ ョン時間は

ステッ

プ とする.更に,シングルラン法

により

の倍額区間を求める.

和崎克己 ･不破 泰 ･中村八束 ･清水英孝

At

2 le P 1

3 e

? L o ^ V

100

0.00001 0.0001 0.001 (丁

図

平均パケット遅延 とJの関係

‑1 0)

‑1 0.

4‑1

平均 パケ ッ ト遅延 に関す る考 察

バ ッファに蓄積可能な最大パケット数が

‑1 0の場合について,パケット発生確率Jと 平均パケット遅延 ( Taで正規化)との関係を図

に示す.国中,実線が解析によって得 られ た億 を示 し

○△がそれぞれ

のシミュレーション結果を示す.解析値 とシミュ レーシ ョン結果 とは良 く一致 してお り,解析の精度が高いことがわかる.

4‑2 バス分割 の効 果 と最適 な分割方法 に関す る考 察

バス分割構成のモデルにおける解析結果を

と同様にシミュレーションによる結果 と 比べる.ここでは,全チャンネル数

Q) を

,パケット転送に要するステップ数 H

,端末バ ッファの容量

‑ 1 0とし,い くつかの

の組合せについて解析する.

シ ミュレーション時間は

ステップ とする.

Jと平均パケット遅延 ( 孔 で正規化)との関係を,図

に示す.図中○がバスの分割をせず

である場合,また△ロがそれぞれ

×2, 8×8でバスを分割 した場合の シ ミュレーシ ョン結果を示す.解析億 とシミュレーション結果とは良 く一致 してお り, バス 分割を行った場合の平均パケット遅延についても, 解析の精度が高いことがわかる.

全体の傾向 として, 低負荷時では, バスを分割 した構成の方が平均パケット遅延時間は小

さ くな り, 分割 した効果が表れている.負荷を上げてい くと,ある

図

では

を

越 えた辺 りで,いずれの場合 も遅延時間が急激に大 きくなる.

′ 1ケ ット処理装置に適 した トークン方式. ミス調停法 と性能解析

^e

]o p

3 e

6 e L o > V

100

0.00001 0.0001 0.001 (丁

図

平均パケット遅延 とUの関係

,バス分割

,H‑1

, T‑1 0)

Fig.8:Avaragepacketdelayv8.gforM ‑ 64,BUSpartitionPxQ‑ 32×2,8×8

, H=1 6

T=1 0.

高負荷以外の場合において,分割方法 ( P

の組合せ)をどの様にすれば,遅延時間が最 小 となるか,以下に考察する.

パケットが発生 してチャンネルのバ ッファに蓄積 されてか ら,そのチャンネルに トーク ンが到着するまでの時間が,遅延時間となる.このため,トークンが途中で通過 したチャン ネル数が少ないほど,パケットの遅延時間は短い.バスを分割 した構成の方が, 分割 しない 構成に比較 して リング当 りのチャンネル数は少な くできるので, ■ 結果, 遅延時間は小 さくな る.この とき,トークンが途中で通過するチャンネル数の平均は,下位,上位 リングが各 々

で, 全体で

となる.

以上 より,分割する場合に

が最小 になるように分割すれば,遅延時間は最 も小 さ い.例 えば

の場合は

の時に遅延時間が最小になる.

5 まとめ

本論文では,ター ミナルサーバの構成に通する,トークンリングを利用 した,新 しいバス 調停の方式を捷案 した.周辺チャンネル数が増えた場合にノヾスを分割することで端末バ ッ

ファでのパケット待ち時間の減少を図る方法 も併せて提案 した.提案方式のマルコフモデ

ルを作成し, 平衡点解析の手法を用いて解析 した.シミュレーション結果 と比較 し解析精度

74

和崎克己 ･不破 泰 ･中村八束 ･清水英孝

を検証 した.また, バス分割構成の場合について最適な分割方法について考察 した.

今後の課超 としては, 提案方式 と他の調停方式 との比較, 提案方式を用いたターミナルサー バの試作 と

上での試験,などが挙げ られる.

謝 辞 この研究の一部は,平成

年度 長野工業高等専門学校教育研究特別経費により 行われた.

参 考 文 献

1)M.K.Craig,M.

Ri c k

,

･

2)W.GeorgeP.

,

,

3)TaubD.M.

,

TUREBUS",IEEEMicro,

γ

.

0.

4)M.K.Vernon.,U.Manber

,

5)M.S.Masud,S.U.Al

a m ,

6

)山本 欧,鳥居 淳,天野 英晴

標準バス

のバスアービタの性能評価", 情処学研報

1 .

7)

不破 泰,中村 八束,清水 英孝,"

重の リング構造から成るキャンパスネットワーク

について‑",倍学論

8)IEEE

,

,

9)ANSI

,

tocol'',ANSIX3.148,1988.

10)S.TaBaka

,

ll)H･Kobayashi

,

'

. 4

pany,Inc.,1978.