椿哥-分享之部落格

題目:

Two MAC frames are transmitted from two stations simultaneously on the 10 Mbps Ethernet that uses coaxial cable with CSMA/CD protocol,

two transmissions collide at the first time. Assume that the packet size is 1518 bytes, and no other frames are to be transmitted.

Estimate the earliest time(starting from the first transmission attempt) that these two frame transmission will be completed successfully.

(此題為有線網路的情況)

題目寫到從要傳第一個frame的企圖後開始計算，

假設現在有兩個Station，A跟B

題目意思即為A、B還沒開始送 (A,B也還不知道第一次送出會碰撞)

u   問題是每個工作站到底要監聽多久才能確定其送出的訊框不會發生衝撞呢？答案是 2a，其中 a 是訊號由同軸電纜的一端傳遞到最遠的另一端所需的時間。而 2a 也正好就是一個時槽時間

因為Ethernet每一個 Frame 的 size 必須大於 64 bytes (512bit)。

64 bytes x 8 = 512 bits

2a =    =   = 51.2 µs

A從送出frame，到知道碰撞馬上停止時,需要花費2a = 51.2 µs(微秒)

A 、 B這時候都知道碰撞產生了，所以進入Backoff，第一次碰撞以後，A跟B都有各自的backoff Î {0,1}  slot，A、B都有兩個可以選。

l   最好的情況就是一個選0，一個選1  (一個slot時槽時間為 51.2 微秒)

u   (比較差的情況就是又選到一樣的slot，碰撞以後，進入第二次碰撞的backoff，Range變成Î {0,1,2,3}，繼續隨機選擇，直到兩個選到不會碰撞，有一方可以傳遞資料。(若碰撞仍需再加倍,加到 {0~1023} )最差的情況差不多是差到兩邊都無法傳送資料，最後放棄，而最差情況則有無數種可能)

而最好的情況A backoff 選到了0，B backoff選到了1（或是A選了1，B選了0。都是一樣的情況），

此處假設A 選了第0，B 選了第1。

A在第0個slot傳遞資料（意即2a(µs)知道後，馬上就使用纜線再重新傳遞資料）

傳遞所花時間為   =1214.4 µs

而B在backoff 一個slot time以後，知道纜線上面有訊號（有人在使用!）便繼續監聽，一直監聽到訊號消失（直到A傳送完畢，纜線空閒）。

l   在傳送前聽到電纜上有訊號則仍繼續監聽直到訊號消失後 立刻將其訊框送出。這個方法稱之為「1-堅持法」(1-persistent)

一聽到纜線是空閒的，B就馬上傳遞他自己的資料，也花了 =1214.4 µs傳遞完成。

所以總共花的時間為

(A、B偵測到碰撞)  + A傳送     + B傳送     = 總共時間

51.2 µs + 1214.4 µs + 1214.4 µs = 2480 µs

l   補充資料:

CSMA/CD 通訊協定運作原理的使用所謂的隨機延遲時間(random delay time) 。其延遲時間的長短由一個亂數決定，以便儘可能使所有參與衝撞的工作站的延遲時間不相同，以避免因為延遲時間相同而造成的再次衝撞。此方法稱為「二元指數後退演算法」(Binary Exponential Backoff Algorithm) 

n ： 連續發生衝撞的次數 (n ≦ 16 碰撞小於等於16次) 。當 n ＞ 16次時則顯示網路的負載太重，訊框因不斷的衝撞而無法傳送。此時該工作站會放棄繼續傳送該筆訊框並且報告情況。

k ： MIN(n,10) ，n 值和 10 的最小值。當 10 ＜ n ≦ 16 時，是為了讓backoff鎖在0~1023之間，r Î {0,1,2...,1023}，表示延遲時間最長為 1023 個時槽時間。否則延遲太長反而較無效率。

r ： 隨機延遲時間。單位是一個時槽時間(slot time) ，其定義是訊號由網路上最遠的二端來回傳遞一次所需的時間(Round-trip propagation delay)。在標準的網路中，一個時槽時間為 51.2 微秒，而0 ≦ r ＜ 2^k，也就是說 r Î {0,1,2....,2^k-2,2^k-1}。

Reference:

[1] http://www.cs.nthu.edu.tw/~nfhuang/chap04.htm

[2]http://en.wikipedia.org/wiki/Exponential_backoff

不知道這篇文章是不是有幫到你(妳)呢?

如果有幫助的話 在下面留個言感謝一下~

是我發文的動力唷^^