kuni_memo @ ウィキ
kuni_memo @ ウィキ

Library > 工学 > プログラミング・アルゴリズム > ネットワーク工学・プログラミング > Note1_スループット

このノートの目標

「Ethernetを半二重で使用した場合（1-persistent CSMA/CD）、最大伝送速度の30%しかでない。」ということが知られているが、どういうことかについて整理したい。まだ途中。

参考 

http://www.hishoutechno.com/pages/tech/IPTEL3-2.html

宮原　秀夫, 尾家　裕二, ...コンピュータネットワーク
Hammond, O'Reilly, ...Local Computer Networks

スループット計算の際のEXCELシート

スループット算出例

表記 

S:スループット:伝送率Gとほかのパケットと衝突しない確率の積、回線を有効に利用する割合
G:時間T当たりに伝送されるパケットの平均数(伝送率)=λT
τ:最大伝搬遅延時間
a:正規化伝搬遅延時間（最大伝搬遅延時間τをパケットの伝送に要する時間Tで割った値）
γ:ジャム信号長

Pure ALOHA方式

  • Pure ALOHA方式とは、 
    AからBへの伝送時間をTとする。その伝送時間の2倍(2T)経過後に、BからAへACKが送信されない場合、衝突が発生したとする。
単純に、必要時に送信するスタイル。
  • スループット 
     S=G e^{-2G}
  • 証明 
    パケットの伝送時間Tに送信されるパケットの合計数が、ポワソン分布に従うものとした場合、
 P_k(T)=Prob [時間Tの間に合計k個のパケットが伝送される]
 =\frac{G^k}{k!} e^{-G}

一方、2Tの間に合計k個のパケットが伝送される確率は、
 P_k(2T)=\frac{(2G)^k}{k!} e^{-2G} 
2Tの間に合計0個のパケットが伝送される確率は、
 P_0(2T)=e^{-2G} 
なので、スループットSは、
 S=G e^{-2G} 

[参考、ポワソン分布に関して]
 P_k(T)==\frac{(\lambda T)^k}{k!} e^{-\lambda T}
 G=\lambda Tとしている。

Slotted ALOHA方式

  • Slotted ALOHAとは 
    回線を時間分割（分割された区間をスロットという、1,,,,,K個まで使用する、理想上は、K=∞を想定）し、パケット送信タイミングの衝突が発生した場合は、ランダムなスロット分送らせて送信する。
  • スループット 
     S=G e^{-G}
  • 証明 
    1スロットの間にパケットが、k個伝送される確率は、
 P_k(T)=\frac{G^k}{k!} e^{-G} 
なので、
スループットは、1スロットの間に、パケット伝送がない確率に支配される。
 S=G\times P_0(T) =G e^{-G}

persistent CSMA

non-persistent CSMA(Carrier Sense Multiple Access)

  • non-persistent CSMAとは 
    伝送路のビジーを検出した際、即、伝送路のモニタを停止し、最大伝送時間ぶんの待機後に再びパケットを伝送する。
  • スループット 
     S=\frac{G e^{-a G}}{G (1+2a)+e^{-aG}}
  • 証明 
    スループットとは、1サイクル当たりに回線を有効利用する割合で決まる。
S=\frac{\bar{U}}{\bar{B}+\bar{I}}
\bar{U}：伝送が成功した期間の平均長
\bar{B}：稼働時間の平均長
\bar{I}：パケットの平均伝送間隔

まず、パケットの伝送間隔は、パケット発生をポワソン分布として、その無記憶性から、
\bar{I}=\frac{1}{G}

次に、パケット伝送後、伝送開始からaの間に、ほかのパケットが伝送されなければよいので、
\bar{U}=e^{-aG}

最後に、稼働時間について考える。
稼働時間は、パケットAの伝送開始時点tからそのパケットAと衝突する最後のパケットが
伝送され始めるまでの期間Yと伝送時間1、遅延時間aの和である。
B=1+a+Y

Yの平均を求めれば、\bar{B}が求まるので、Yの平均を求めよう。
F_Y(y)=Prob[a-yの間にパケットが伝送されない]
=e^{-G(a-y)}

\bar{Y}=\int_{0}^a y dF_Y(y) =\int_{0}^a Gy e^{-G(a-y)} dy
=a-\frac{1}{G}(1-e^{-aG})
これから\bar{B}を求めることができて、
\bar{B}=1+2a-\frac{1}{G}(1-e^{-aG})

1-persistent CSMA

伝送路のビジーを検出した際、即、最大伝送時間ぶんの待機後に再びパケットを伝送する。

S=\frac{G[1+G+aG(1+G+aG/2)] e^{-(1+2a)G}}{G (1+2a)-(1-e^{-aG})+(1+aG)e^{-(1+a)G}}

  • 参考資料

    L.Keinrock and F.A.Tobagi,"Packet Switching in Radio Channels: Part I-Carrier Sense Multiple Access Modes and Teir Throughput-Delay Characteristics", IEEE Trans. on Communications

p-persistent CSMA

伝送路のビジーを検出した際、確率pで伝送路のモニタを継続し、再びパケットを伝送する。 確率(1-p)で、最大伝送時間ぶんの待機後に再びパケットを伝送する。non-persistent CSMAとp-persistent CSMAの中間の位置づけ。

CSMA/CD(Carrier Sense Multiple Access with Collision Detection)

  • Ethernetでは、1-persistent CSMA/CDを採用している。

S=\frac{G e^{-aG}}{G e^{-aG} + \gamma a G(1-e^{-aG})+2a G(1-e^{-aG}) + (2-e^{-aG})}

  • 参考資料

    F.A.Tobagi and V.B.Hunt,"Performance Analysis Carrier Sense Multiple Access with Collision Detection", Computer Networks

「Note1_スループット」をウィキ内検索
最終更新：2016年02月28日 16:57