ループ電子計算機網のトラヒック特性に関する一考察: University of the Ryukyus Repository

Title

ループ電子計算機網のトラヒック特性に関する一考察

Author(s)

照屋, 健

Citation

琉球大学理工学部紀要. 工学篇 = Bulletin of Science &

Engineering Division, University of the Ryukyus.

Engineering(8): 113-124

Issue Date

1975-01-30

URL

http://hdl.handle.net/20.500.12000/26295

琉球大学理工学部紀要(工学篇)

J

レープ電子計算機網のトラヒック

特性に関する一考察

照

屋

健 *

A C

o

n

s

i

d

e

r

a

t

i

o

n

o

f

T

r

a

f

f

i

c

C

h

a

r

a

c

t

e

r

i

s

-t

i

c

s

i

n

a

Loop Computer Network

Ken

TERUYA Summary:

This paper reports the analysis of traffic characteristics of a loop computer network. The analysis is based on the assumption that: (1) a packet is transmitted to the unilateral direction; (2) in each station

，

waiting of messages in the form of packet in the queue is under full-load condition; (3) the packet has a constant length of M.

In such a model of loop system

，

the flow condition of packet becomes jammed traffic and there would be no vacant slot on the main transmission line

，

therefore

，

chance to transmit a packet

，

for a particular station

，

comes only when the station receives a packet from the other station.

Let Pij (iキj) be the proportion of flow (packet) emerging from station i and destined for station j. We define as symmetric case when pij is uniform regardless of the station

，

and as asymmetric case when pjj is not. In the symmetric case

，

if we regard the probability that (N・l)th type of packet exists on the slots between stations， after a transition of main line slot， as state vector， the state vector at one slot unit time is described by Markov chain. N denotes the number of data stations which are arranged around the loop-shaped main transmission line. The steady state vector is obtained by using the transition matrix. The information transmission factor of steady state is calculated by applying the steady state vector. As to the factor

，

the symmetric case system assures the minimum value of1J(N・1). The same technique of analysis as the symmetric case

，

being applied for the asymmetric case analysis

，

shows that the some sort of control is necessary in order to give fare chance of baJanced usage of the main line sJots for the stations arranged.

The transient traffic characteristics of the symmetric case are analyzed for minor stations. The analysis shows that about twelve steps of transition are enough to be steady for the information transmission factor. 113

1

.

は じ め に コンピュ{タ・ネットワ{クとは，地理的l己独立に 分散しているそれぞれの電子計算機を高速度通信回線 受付:昭和49年4月30日 *琉球大学短期大学部電気工学科 で連結し，使用者が相互間で，それぞれの個性あるリ ソ{ス(資源)を利用できるようにした通信網形態で あるといわれている。コンピュータ・ネットワ{クは トポロヲー， リンク，経路選沢，回線容量，メッセー ジとパケットの構成，通信制御用ミニコン，ホストコ ンピュ{タ等と多種多様の問題を含んでいる。ネット

114 ループ電子計算機網のトラヒック特性に関する一考察 ワーク11:関する特性を実験的な方法で求めるのは，多 くの場合，莫大な経費を伴うので実際的でないことが ある。このようなときには，電子計算機によるシミュ レーションや机上でのモデルによる解析等が有効であ る場合が少なく江い。筆者はル{プ・システムについ て研究する機会を得たので，そのトラヒック特性等l乙 関して報告する。本報告はル{プ・コンピュータ・ ネットワークのトラヒック特性について解析したもの で，解析は次の仮定に基いておこなわれた。(1)パケ ットは単一方向に伝送される。 (2)メツセ{ヲはパケ ットの形で待ち状態にあり，パケットの待ちは full. loadの状態である。 (3)パケットは一定の長さMを 有する。このようなル{プ・システムのモデルにおい ては，パケット伝送のトラヒックは過密の状態とな り，主回線上のスロットには「空き」 がなく，特定の ステ{ションにとって，一個のパケットの伝送が可能 なのは，他のステーションからパケットを受取る場合 のみである。今.pij(iキ j) を ス テ { シ ョ ンiか ら jへ伝送されるパケットの生起確率とする。 pljが ステ{ションIL関係なく同一である場合 を 対 称 系 と し，同一でない場合を非対称系

ε

した。対称系の場 合，ステ{ション聞のスロット上に，回線のスロット の一つの遷移の後K. (N - 1)種類のパケットが存 在する確率を状態ベクトルと見なすとースロット単位 時の状態ベクトルはマルコフ連鎖によって表現できる ことが分った。ことでNはループ状の主回線に沿って 配列されてし、るデ{タ・ステーションの数を表わす。 定常状態ベクトルは遷移行列を用いて得られ， 定常 状態の情報伝送率は定常状態ベクトノレによって算出さ れた。同伝送率は，対称系の場合には最小値として l/(N-l)の値が確保されることが分った。対称系 と同様な手法で，非対称系の解析がなされたが，これ により，各ステーションにとって公平なスロット利用 を期するためには適切なスロット配分のためのある種 の制御が必要であるととが分った。限られたステ{シ ョン数の場合のトラヒック過渡特性について解析した 結果 ， 情 報 伝送率 は 約12ステップ程度の遷移があれ ば，定常状態 K落着くことが分った。

2

.

ループ・ネットワークの概略 電子計算機ネットワ{クにおけるループ・システム の解析は

J

.

R. PIERCEllゃ

J

.

D. SPRAGINGS2) の論文に見られる。ネット・ワークは数個の閉じた環 (ループ)によって構成されていて，そのJレ{プ上を パケットと呼ばれるデ{タ・ブロックが循環しながら 伝送される。図1はループ・コンピユ{タ・ネットワ ークの全体の構成図であり，大中小の各Jレープの連絡 から成り，小ル{プはローカル・ループと呼ばれる最 小の単位のル{プである。図2はローカル・ループの 基本的な構成図である。以下図2について話を進めて 行く。図2でA.B. Cはステ{ションを表わす。デ ータ・ソースはステ{ションBI乙結ぼれている。 (A とCについては後述する。) トラヒックはステ{ショ ンからステーションへとループに沿って単一方向l己流 れて行く。ステーションBでは，出力として，ヘッダ をつけられた固定長のパケットが送り出される。メッ セージは数個のパケットで出来上っているときもあ る。パケットは，回線が空いておれば，直ちに回線上 に載せられる。載せられたパケットはステーシヲンB から他のステーションBへと各ステーションを通過し ながら目的地へと向う。その途中で，パケットの宛名 は，その特定のステーション宛のパケットでないかを 見るために， 各ステーションで調べられる。パケット がその特定のステ{ション宛のものであれば，回線上 から取り除かれる。その際，特定のステーションはパ ケットを受取ったあとの空スロットを利用することが 出来る。利用しないときは，次のステ{ションへ空ス ロットを譲ることになる。回線上に一度載ったパケッ は，とれから回線上に載ろうとするパケットに対し優 先権を有し，目的地へ着くまで回線上から取り除かれ ることはなく，コンベア・ベルト上を載って行くかの ように，遅滞なく目的地へと届げられる。もし，ある ステ{ションにとって，利用したい回線に「空き」が ないときは，作られたパケットは回線11:

i

空き」が生 ずるまで一時的に通信制御用ミニコンの記憶装置に入 れられる。あるステーションで送り出されるメッセー ジが数個のパケットで出来上っているときは，そのス テ{ションを通過して行く他のステーション宛のパケ ットのために，書き込みが一時中断されることもあ り， もし中断されれば，回線の「空き」を待って，書 き込みが再開される。このようなシステムでは，ある ステ{ションが主回線上 l乙一個のパケットを載せるこ とが可能なのは.(1)トラヒックに「空き」がある場 合.(2)主回線から一個のパケットを受取る場合であ る。以上がステーションBについての説明である。き て，ステーションAII:はニつの基本的な機能がある。 第ーはループの同期をとることで，第二は宛先不明の パケットによるループ・トラヒックの占有を防ぐこと

琉球大学理工学部記要(工学編) 115

Fig 1. General features of loop system である。パケットが始めてステ{ションAを通過する とき，そのパケットのヘッダがステ{ションAで記録 される。二度もヌテーションAを通過するようなパケ ットがあると，そのパケットは回線上から除かれてし まうか，又は発信地と着信地の宛名を入れかえる操作 をほどとして，発信地へと送り返される。ステーショ ンCは小ル{プと中ループ聞の連結というようにルー プ問の結合をする役割をなす。小ル{プ外へ送られる べきパケットがあると，

c

でバッファリングされたの ち，中ループの回線上l乙載せられる。

3

.

ループ・システムのモデルの解析 解析は図2の小ループ内のステーション間の通信の みを取り扱い，便宜のためにステーションAとステー ションCを除き，ステ{ションBだけが存在するもの とする。図 2のシステムにある条件を付して作ったモ テツレが図3である。図3のモデルにおいて，すべての Fig 2. Local loop ステ{ションのバッファ内でのパケットの待ち状態が full-loadであり，パケットは単一方向(時計方向) に誤りなく送受されるものとする。メッセ~Ò/は一個 のパケットで構成され，パケットは一定の長さMを有 するものとする。バッファ内には

(N-1)個の種類

のパケットがあり，タイプlのパケットは任意のステ {ションから，隣接する第1番目のステーションへ送 られ，タイプ2のパケットは任意のステーションから 数えて第 2番目のステ{ションへ送られるというよう に (N-l) 種類のパケットが順次送られていくも のとする。ステーションiからステーション

i(

i

=

1， 2， ..…・， N -l)へ送られるパケットの生起 確率を pijとする。 ここで， 2:.:pij = 1 (iキj)。 Full-loadの場合のトラヒックは過密の状態とえZり， 空スロットはなく，自分のステ{ションでパケットを 受取る場合にのみ，パケットの伝送が可能であるとい う制約された状態となる。 station# 1. / ¥

、

~ di_rection of flc ノハぞ station 非~j~ ーで - _/v/ station# i

旬

、

ー

-

-

c

J

-

-

_

.

.

.

.

.

.

.

Fig 3. Model of loop system.

Jレ{プ電子計算機網のトラヒック特性に関する一考察 即ち，自分よりつぎのステーションK移るものを 1以 下遠い頓に番号も大きくなり， 2， 3，…， (N-1)と する。あるステーションを通過したのちの， (i-1) 番目のステーションとi番目のステーション関のスロ ット上に存在する (N-l)種類のパケットの存在確 率を状態ベクトルと考えると，これはステーション 毎に遷移を受けるわけであるが，これはマルコフ連鎖 をなし，その遷移確率行列

p

.は式

(1)のようにな る。 3) 4) 定常態特性 対称系の場合 任意のステーションから他の (N-l)伺のステ{ ションヘパケットを伝送する際，あるステーションK 存在する (N-l)種類のパケットを考える。との パケットの発症する確率が，各ステ{ションについて 同じでみるものを対称系とする。 との場合はPij=Pi ( i =1，2，…， N j =1，2，…， (N -1)) となる。 116 3-1 1) Note : Symmetyiccase (1) r= 3 (p

，

:

LARGE) 0.8 0.6 0.4 0.2 ~

o

h

υ

〈 何 Z

。

炉開4

a

ト4 ~ rf)

Z

〈 白d E-< Z

。

炉4 ド 〈 ~ ~

。

与4 Z ド・4 4 3

ARRANGED

Change of information transmission factorvs.

N

Stations.

STATIONS

OF

NUMBER

Fig.4 (1)

凡

0

・

・

・

・

・

・

・

・

・

・

0

a E E ' ハ U n 門 . n V 1 1 n M I t l

ハ

U

・

・

・

・

・

・

・

・

ハ

υ

ー

ー

P

_J

117 状態ベクトルをX = (X1• X2• …. XN-1)とする と，定常の状態は式(2)を解いて得られる。 琉球大学理工学部紀要(工学篇)

P

.

は即約で，非周期的であるので，定常極限分布 が存在する。時間(選移)が十分経過したのちの極限 (2)

0

1

0

・

・

・

・

・

・

・

・

・

・

0

a E E '

・

.

・

.

ハ

U

仇

401

・

n H

_，

q l 内 U

・

・

・

・

・

・

・

・

ハ

U

•

X

，

X

₂

X

_N・1

ー

.

-E 内_t vAVA--.... となる。乙とでいう情報伝送率というのは，ある特定 のスシーションにとってのスロット利用可能状態(伝 送可能状態)の出現確率である。情報伝送率 Tsはパ ケットの生起確率の分布やステーション数NI乙依存し ている。 今.Pl>P2>…・・・>PN-1としたとき

X

_N・1 ここで .tはベクトル X の transposeを表わす。 式(2)を解いて，次の結果を得る。 (3) Xk =

C

さ〉)/(宮川

T

.

を情報伝送率とすると

T

.

=

I

/

C

古川

(4) (5) rN-1-rN-1 (P1 = ~A; _{r N-l-} r> 1) 1

Y

.

.

.

!

= P3 = ・-…=ぞ旦ニ!= _1_ Pl P2 PN-2 r Pl < P2< …… <PN-1 としたとき で， (6) (P12E

￡

さ

了

，

r>l) V A

一 一

N

一

N

P

F

一 一

h

一

h

h

一

h

のような分布を有する場合は，情報伝送率Tsは次のようになる。 rN-rN-1-r

+

1 rN-Nr十CN-1) (P1 > P2・…・・・・>PN-lのとき)

(

7

)

Ts = (8) (Pl<P2 =…・・・=PN-lのとき) Ts

=す

Ts=rN-rN-1-r

+

1 (N-l )rN-NrN-1

+

1 (9) の二つの曲線に比べて急な勾配で

t

むんでいるのは，乙 のような理由にもとずく。式

(

7

)

において. rを大き くしていくと limTs = 1となる。乙の場合の生起確 N→∞ 率の分布は Pl= (rN-1-rN-2) / (rN-1-1). P2 = (rN-2-rN-3)/(r-l) .……であるので rを大きくす ると.Pl= 1. P2 = P3 =…… =PN-I=Oとなる。

E

日 ち，とのような分布のとき，情報伝送率Tsは最大値 Ts max= 1を有する。式(9)において. rを大きく していくと.lim Ts= 1/ (N-l)となる。乙の場 r-o

。

(P1 < P2 く・…・・ <PN-1のとき) 式

(

8

)

と式

(

7

)(

9

)

においてr=3. r=2とした 場合のステーション数NI乙対するTsの変化を図 41乙 示した。式(7)において. Nを限りなく大きくした場 合は limTs = (r -1 ) / rとなる。乙の極限値の式 N→∞ でr=3のとき. Ts = 2/3. r = 2のとき. T =1/2 となる。図4の曲線 (1)(2)が，それぞれ 0.666. 0.5 の一定値に落ち着いているのはそのためである。 式(8)と(9)において. Nを限りなく大きくすると lim Ts = 0となる。図 4の曲線 (3)(4)が他の (1)(2) N→∞

ループ電子計算機網のトラヒック特性l乙関する一考察 起こり，その最大値 Tsmax は Tsmax.= 1とな る。 Tsの最小値 Tsmin.は Tsmin.=1 /(N-l) となる。とのときの生起確率の分布は， Pl=P2=

…

…

=PN-2= 0， PN-l= 1で，とのときに最小が起乙 る。 2) 非対称系の場合 あるステーションから他の

(N-

1

)

個のステーシ ョンヘパケットを伝送する際 fr.，あるステーションl乙 存在する (N-l)種類のパケットを考えると， ζの パケットの発生する確率が各ステーションで異なって いるような系を非対称系とする。 ステーシヲンiにおける各タイプのパケットの生起 確率をPiI(iキj，j =1， 2， …..， N-l) とした が，今，線路上で伝送される各パケットの割合をステ 合の生起確率の分布は pl=(r-1)/(rN-1-1)， P2= (r2-r)/ (rN-l-1)

，

.

.

.

・

H

・

.

.

，

PN-l= (rN-l-rN-2)/(rN-l-1)であるので， rを大きくしてい くと， Pl=P2=

…

…

=pN-2= 0， pN-l= 1となる。 即ち，乙のような分布のとき，情報伝送率Tsは最小 値 Tsmin= 1/ (N -1 )を有する。又， ζれらの乙 とは，式(4)を変形するととによっても，同じ結果が N-l Pl= 1 -:EPiであるので，式(4)は次 i=2 のように変形される。 Ts= 1/( 1 +p2+2p3+

……+

(N-2 )PN-l) (10) 式(10)において.生起確率Piは非負であるので.Ts の最大は P2=P3=.

…

・

・

=PN-l=O，Pl=lの場合l乙 118 得られる。 RATIO OF FLOW ;!:1・#3=1:3 0.4 0.5 P13(

=

P31) 0.2 0.5

z

。 阿 ' H ︿ ↑

ω

図。︿同向 OM 同 O H υ ︿ 旬

z

。 H の の H 2 m Z ︿ 凶 い Z O H ' H ︿

E

M

嗣 O 九 回 Z H 1.0

20

同_{l H} ︿ L F ω 出

υ

︿凶旬。 M 向 。 hG ︿ 向 同 Z O H ω ω ロ 占 的 乞 ︿ 出 L F Z O H ' H ︿ 刷 局 凶 O h 嗣 Z H (b)

z

。 H ' H _︿いの出

ω

︿同民。 M 問 。 ド

υ

︿ 凪 Z O H ω ω H 2 ω Z ︿ 凶 い ZO 同 ' H ︿

E

M

嗣 O h 同 Z H (a) 0・STATION# 1 0・STATION# 2 ...:STATION # 3

z

。 H ↑︿ド

ω

国

ω

︿凶陥 OM 問 。 L F Q ︿ 仙

z

。 回 一 ω 同 湿 の Z ︿ 凶 ド Z O H ' H ︿室凶。凪 Z H 1.0 (c) (d)

Change of transmission factor of each station (N =3. asymmetric case

，

steady state) 0.4 0.6

P13(= P目)

1

1

9

のスロット上11:存在するパケットの存在確率の状態ペ クトルを示し，ステーションを一回通過する毎IC.， つ ぎの遷移を受ける。 琉球大学理工学部紀要(工学篇) ーション iから見たとき (YI1.Y12.……YI(Nー))と する。 y= (Yll， Y12， .・.H，・ YN. (N-l).……， YN.l.……， YN. (N-l))は隣接するステーシヲン間

(

1

1

)

p

，

0

・・・・・・

0

0E1.

O

~-1

0

・・・・・・・・

0

。

o v

-- a

v

P

_N

ー

ー

p

d

(12)

P

I

は次式で示される。

句

恥

同

忠

日

.α.-2'

…

γ

.

.

.

.

R

N

q

1

.

…

.

.

.

一

.

R

巳

巳

は

i-2

~i巳巳.

1 0.. .

.

.

0

0...0 0

o

1

0

・・・・・・・・・・・・

。。

。

。

乙乙でOは要素がすべて0の (N- 1) x (N - 1)の行列であり，

ー

ー

R

i = 1

，

2. ……. N ¥ paNは次のようになる。 式

(

1

1

)

は周期

N

を有する

c

y

c

1

ic

c

h

a

i

n

になり，

肝

Pi"PN

R・~....p' (13)

。

pN:

d

R・R・"~H

。

ロ

o

ループ電子計算機網のトラヒック特性に関する一考察 今.PC1=Pl P2 ...PN. PC2=P2 Pa ...Pl.

…

.

PCN=PNPl

…

PN-lとし.PC=PaNとおけば，式(13)は 次のようになる。

P

c

l

円=

今，式 (14)の部分連鎖を次のようにおく。

I

t

=

(1】 "'1t (1) m21 (1) '''12 -(1) 11122 (14)

P

c

N _(1) • • • • • • • • • • m1t_N・I 一 一(1)

.

.

.

.

・

・

・

・

・

・

π12，N

・

1 (15)

m~_~

_N・1.1 ( j 】 ( 1 )

"

司

_'''N・1，2

・・・・・・・・・・"冒

'''N・I，N・l 式 (15)は既約で，非周期的であるので，極限分布 が存在する。 Pcin(nは 遷 移 の 数 を表わす)におい て

.N

→∞としたときの極限状態ペクトルを

Y

=

(

l

)

CY 1 (i).Y 2(i).

…

.

YN-l(i)

コ

(

i =1. 2.

…

.

N) とすれば極限状態は次式を解いて得られる。

Y(

i)=

Y

(i)・

P

c

i

(16) 式 (16)を解いて得られた結果を次式のようにおく。

Nk

(i) Yk(i) = ー で_Dk← (i) (17) 式(17)でk=1としたときの結果を各ステーショ ンでの情報伝送率 Te(i)とすると， 乙乙で， N

，

(i) Te(i)

=芯お了

(i =1. 2.

…

・

・

・

.

N) (18) 系全体としての情報伝送率を

T

aとすると， N-l

Ta

=

ミ

Ti ₍₁₉₎ N 式(18)についての一般式を求めるのは容易ではな い。今，非対称系の特性を調べるために，最も簡単な 配列のケースとして，式(18)においてN=3の場合 について示すと次のようになる。 1-m22(i) Te(り =1 +m12(i)一m22ω(i =1.2， 3) (20) mll (i)= (Pi，i + 1)

・

(Pi十1，i+2)

・

(Pi十2，i)+ (Pi，i +2)

・

(Pi十2，i)+ (Pi，i十1)

・

(Pi+1，i) ) m12(i)= (Pi，i + 1)

・

(Pi十1，i十2)

・

(Pi十2，i)十(Pi，i+2)

・

(Pi+2，i十1)

I

う (21) m21 (i)=Pi+ 1，i+2)

・

(Pi十2，i)+ (Pi + 1，i)

I

琉球大学理工学部紀要(工学篤) 但し， i

+

1

=

i -2 (mod 3) i

+

2

=

i -1 (mod 3) 121 図5はステーションが3個 の 非 対 称 系 の 場 合 の 各 (遷移の数)を要するのであろうかということは興味 ステーションの情報伝送率の推移を示す。 悶図は， のある問題である。乙乙では対称系の場合で，極く限 P13=P31とし，第2ステーションの生起確率をパラ られたステーション数について，生起確率がある種の メータとして P13(=P31) が 0~1. 0 の変化をした 分布条件を有する場合の過渡情報伝送率について考え 場合の3個の各ステーションの情報伝送率の変化を示 てみる。 しているもので，三つの曲線が一組になっている。例 a) ステーション数が

3

伺

(N=3

)の場合

えば，図

5(b)

での曲線(企印)は第

2

ステーション 式

(

1

)において，

N=3

とすると での第1と第3ステーションへ伝送されるパケットの 生起確率をそれぞれ1: 3としたときの第3ステーシ ョンの情報伝送率の変化を示す。図5より分る乙と は，特定の2個のステーション(この例ではステーシ ョン詳1とステーション詳 3) 聞の通信が密になって 来ると，ステーション持2の情報伝送率が，そのステ ーションの通信の比率に関係なく，圧迫され，遂には 通信不能な状態l乙追い込まれてしまう乙とである。乙 のようなループ・システムでは，交通が密になって来 ると適切なスロット配分のためのコントロールが必要 であることが分る。 3-2 過渡特性 これまで定常態特性についての関係式を導いてきた のであるが，定常態へ達するまでにどれだけの時間 こζで，

T

= (

~了)，

ト 市

(

!

1

?

)

式(24)を解いて ー + n n o a 。 a nynv n n

、 ，

J 、 、 a J 噌 B -噌 E 4

一

一

( (

+

一

噌_i 噌_i ， ， E E l --

、

一@& 一 n v 一 q L l 一 十 一 噌 4 - n v

一 一

n s

p

民 =(

1

:

)

:

P

(22) 式(22)の固有値には重根がないから， Psはある正 則行列

T

によって対角化が可能である。対角化された 行列を

A

とすると，行列は次のようになる。 A = ( : : 2 ) (23) n遷移後の行列

P

:

は次のようにして求められる。 P~ =

T. A

n・

T

-

l

(24) P2ー(_l)np2n十1

1

P2+ (一 1)P2n n ) (25) 今，初期ペクトルを(1， 0) とすると T(n)-

1

ヒ

1

止血竺

1 3 - P1十2P2 P1十2P2

f

旦し， Taは過渡情報伝送率を表わす。 生起確率が4:1， 2:1， 1:1. 1:2のそれぞ (26) れの場合について式 (25) を用いて計算して求めたの が図6(a) である。

Jレ{プ電子計算機網のトラヒック特性I乙関する一考察

ロ

2 1.0 INITIAL STATE(l， 0， 0) 1 : 1 : 1 9 : 4 1 3 : 2 1 (1) (2) CASE OF N=4， 0.5 M 問 。 ド

υ

︿ 旬 Z O H の の H 湿 の Z ︿ 出 L F Z O 同 1 F ︿冨凶 O h 同 Z H (a) INITIAL STATE (1， 0， 0) (3) 4 : 1 2 : 1 1 1 1.0 (1) (2) CASE OF N=3， 0.5 出 O L F O ︿ 弘 Z 。 同 m w m H M a ω Z ︿凶 ' H Z O H L F ︿ E M 同 O K 同 Z H 12 II 10 9 8 5 6 7 n (TRANSITION) 4 (b) Transient information transmission factor (Symmetric case) Fig.6

琉球大学理工学部記要(工学籍) 123 b)ステーション数が4個 (N=4)の場合式(1)においてN=4とすると

r

Pl P2 pa 1

P

s

=

I

1 0 0

I

(27) ¥ 0 1 0 ) 式(27)の固有値は次式を解いて得られる。 て，式 (29)のように対角化される。 ( 1 0 0 ) A = I 0 rl 0 I ~ 0 0 r2 } (29) ( λー1)Cλ2+ (P2+2ps)λ+pa) = 0 (28) ととで， 今，固有値がすべて相異なる場合についてのみ考え るととにし，式(28)を解いて得られる相異なった固有 をrl，r2(固有値の1は除く)とする。式(27)は固 有ベクトルによって作られる次の正則行列

T

IZ:ょっ 、 ‘ ， ， 。 a 、 、 ， ， 。 h " 。 命 。 a V A q a 省 A -v a v A L

一

一

日

1

1

( (

一

一

、 ‘ ， J 。 a v 且 2

一

1

r

1

r

-， e_‘ 、 -円 一 l ， z . . . . . . . . . . . ， ， ， .• _{、 、} 一 p -32h 唱 ・ A 一 、 、 ， ， ， 一 。 “ 一 V A -V A

-T

n遷移後の行列

P

は次のようにして求められる。 psn = T •

A

.

T-l 式(32)を解いて ‘ 、 E E E

・

E

・

E

・

-E E ， ， o e 。 . 。 a l l -﹄ V A r 噌 J 9 ・ ・ -A -A -T A V -1 J 噌 ' ム 噌 目 ・ 畠 唱 E ム ， ， .E

・

E

・

-Z E E E

・

E

・

-E E‘ 、

一 一

T

(30) 、 、 E E E E

・

E

・

-E ' E ， ， e e 。 a V A 、 ‘ ， ， 。 A W -2 2 -a v a 唱 A

- 一

f e e -a -r r -1 2 r ‘ 、

r

h 一 ₍₃₁₎ (32) ( (rl-ra) -rln+2( 1 -r2) +r2n+2( 1 -rl)ー(rl-f2)(rl + f2)十 psn = 1 3

I

(rl-r2) -rln+1( 1 -r2) +r2n+1( 1 -rl)ー(f1-r2) (rl + r2) + (rl-r2)・2::ipl

I

i:;;-l~ ~ (f1-r2)ーrln+l(1 -r2) +r2n (1 -rl)ー(rl-r2)(ロ+r2)十 (1 -r2) (1 +C2)rln+2ー(1-rl) (1 +rl)r2n+2+ rlr2(rl-r2)ー(1-r2)r2rln+2+rl( 1 -rl)r2n+2) (1 -r2) (1 +r2)rln+1ー(1-f1) (1 +rl)r2n+1+ rlr2(rlーr2)ー(1-r2)r2f1n+1+rl (1 -rl)r2n+1

I

(33) (1 -r2)( 1 +r2)rln ー(1-rl) (1 +rl)r2n + rlr2(f1-r2)一(1-f2)r2f1n +f1(1 -f1)r2n ) 今，初期ベクトルをN=3の場合と同織に

(

1

，

0

，

0

)

とすると，過渡情報伝送率は次のようになる。

i

，

_

rtn+2- r2n+2 rt r2 (rtn+1 - r2n+1)

1

T4(n)=

-

，

-

一

一 {

~ '. 1 f1 -r2 rl - r2 ) 2::ipi 生起確率が9:4:1， 3:2:1， 1:1:1，

1

:

2

:

3

のそれぞれの場合について，式

(

3

4

)

を用 いて算出し，その結果を図示したのが図 6(b)であ る。図 6(a)，(b)を見ても分るように，情報伝送率 は約12ステップ程度の遷移があれば，定常状態i乙落ち 着く。生起確率の比が近くは小さく，遠くが大きいよ うな分布のときは，定常へ達する時間も長く，定常値 も小さい。生起確率がその逆の比を有するような分布 のときは，定常へ遥する時間も短かく，定常値も大き い。初期ペクトルが (0，1， 0) (0， 0， 1)のとき (34) は 図6(a) (b)の値が全体的に，それぞれ1ステッ プ， 2ステップづっ右へシフトするだけである。任意 の初期ベクトル (a

，

s

，

1)のときは三つの場合によ って作られるリニア・コンビネーションになる。

4

.

結 言 対称系の定常態特性において，生起確率の 分 布 が Pt， P2.…の順i乙次第に小さくなるような分布では， ステーション数Nを増やした場合には情報伝送率はあ る定常値に落ち着くが， Plo P2.…のl頃i乙次第に大き

124 ループ電子計算機網のトラヒック特性1c.関する一考察 くなるような分布では情報伝送率は急激に減少してい る。このことから，公平なスロット配分を行なうた めには生起確率の分布状況やステーションの配列を 考慮に入れる必要があるととが分る。定常状態の情 報 伝 送 量 を ^(packet/sec)とし，回線容量を Cp (packet/sec)とすると，パケットの毎秒の伝送量は N-l Cp/ ( .L: ipl) (packet/sec)となり，最悪の場合でも Cp/ (N -1) (packet/sec)の量が送り出される。 非対称系における系金体としての系情報伝送率(但 し， N= 3の場合)の最大はP13=0.5(0:1)の ときにおζ仇 そ め 最 大 値 は0.76である。乙のよう な生起確率の分布が与えられたときは，系の最大伝送 能力は0.76と見倣せる。 対称系の過渡特性では，式(3)によっても分る乙と であるが，情報伝送率はステーション数が少なけれ ば，定常値が大きくなっている。生起確率相互間の比 が大より小へと次第に小きくなるような分布の場合は 3または 4の遷移で定常値1c.達するが，相互間の比が 小より大へと大きくなるような分布のときは遷移数も 大きくなり， 11または12の遷移数を要している場合も あるが，定常状態1<::達する時間(遷移の数)は割合 1<:: 早いことが分る。 対祢形系の問題は数学的には扱い易いものではある が，実際の場合として起乙り得るのは希であると云え る。しかし，ステーションへのメッセージの到着とス テーションのアウトプットとの関係を知る上での基本 的な考え方の出発点ともなるので，将来，より一層複 雑なモデルの解析を行なう際の土台となり得る乙とを 考えれば，基本的1<::大切な解析のーっと云えよう。対 称系や非対称系の場合も含めて.full.loadよりきつい 条件はないのであるから，その条件下で得られた値 は，ある意味では，最低限の値を保障しているとも 云える。乙れらの{直は実際l乙ループを構成する際のス テーション数の決定やステーションの配置を考える際 の参考になるものと思う。 本報告では，すべてのステーションでのパケットの 待ち状態がfull-loadの場合を考えたのであるが，メ ッセージの到着は，より実際的な場合として，ポアソ ン分布，幾何分布やその他の分布をなす場合が多いの で.full司loadでない状態での解析を試みていきたい。 対祢系の過渡特性は重根の場合も考慮1c.入れると生 起確率の分布やステーション数の違いによって色々な ケースが出て来るととが予想されるので，非対称系の 場合の過渡特性の問題も含めて，今後も更に検討して いきたいと思う。

5

.

謝 辞 本研究1<::関して御指導ならびに御鞭遥下さいました 東北大学電気通信研究所の野口正一教授，ならびに東 北大学応用情報学研究センタ一所長，大泉充郎教授に 深く感謝致します。また，絶えず温かく励まして下さ いました東北大学応用情報学研究センターの藤田勝美 助教授，ならびに日頃から熱心な討論をして下さいま した大泉・野口両研究室の皆様方に深く感謝し，お礼 申し上げます。

6

.

参考文献 1) J. R. Pierce“Networks for Block Switching of Data". B.S.T. J.. Vo1.51. No.6. pp. 1133 ~1145. July-August. 1972 2) J. D. Spragings "Loop Transmission System Mean Value Analysis'

二

IEEE Trans. Com-mun.. COM-20. No.3. pp.592~602. June. 1972 3) 照屋，野口，大泉“計算機ループネットワークシ ステムにおけるパケット伝送のトラヒックに関す る一考察"昭和48年度電気関係学会東北支部連合 大会， 2F -3， p. 202. 1973年8月 4) S. Noguchi， N. Shiratori. K. Teruya. J. Oizumi“On Characteristics of Loop Comput-er Networks"， 7th HICSS. Univ. of Hawaii. January 1974