「Library/工学/プログラミング・アルゴリズム/ネットワーク工学・プログラミング/Note1_スループット」の編集履歴（バックアップ）一覧に戻る
#navi(Library/工学)
#contents
----
*このノートの目標
>
「Ethernetを半二重で使用した場合（1-persistent CSMA/CD）、最大伝送速度の30%しかでない。」ということが知られているが、どういうことかについて整理したい。まだ途中。
<
----
*参考
http://www.hishoutechno.com/pages/tech/IPTEL3-2.html
宮原 秀夫, 尾家 裕二, ...コンピュータネットワーク
Hammond, O'Reilly, ...Local Computer Networks
----
*スループット計算の際のEXCELシート
-&ref(通信スループット計算.xlsx);
----
*スループット算出例
>
表記
<
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
<
