Homework 11/10/2007

In the talk, we introduced the evolution of contention based protocols:
1. ALOHA 2. CSMA (Carrier Sense Multiple Access) 3. CSMA/CD (collision detection) -> IEEE 802.3 (Ethernet, 100M, 1Gbps)
Problem 1. Why does Pure Aloha perform worse than Slotted Aloha?
Pure Aloha : unslotted Aloha: 較簡單,非同步,封包不會等到在slot的開頭才傳送,會增加碰撞的機率P(success by given node) = P(node transmits) .P(no other node transmits in [p0-1,p0] .P(no other node transmits in [p0-1,p0]= p . (1-p) . (1-p)P(success by any of N nodes) = N p . (1-p) . (1-p)… choosing optimum p as n -> infty ...= 1/(2e) = .18 Slotted Aloha : 時間分割成等長的slot,節點在下一slot的開頭就傳送封包,如果發生碰撞：以p的機率重送封包直到成功為止,假設有N個節點要傳送封包,每個slot以p的機率傳送封包,成功傳送的機率S 為單一節點: S= p (1-p)(N-1)任意N節點 S = Prob (單一傳送) = N p (1-p)(N-1)… choosing optimum p as n -> infty ...= 1/e = .37 as N -> infty最佳情況：37%頻道使用率Problem 2. According to Textbook pp. 2-48~2-51, why does 1-persistent CSMA have lower throughput than non-persistent CSMA when generated traffic rate is higher than 1 (G>1)? Why does 1-persistent CSMA have shorter latency than non-persistent CSMA?
1-Persistent CSMA : 先偵測通道是否有載波，若是沒有立刻送出 frame  若偵測到有其他機器在使用通道，則持續偵測下去，等候到通道閒置時立刻傳送 frame。  送出 frame之後，等候接收端的 ACK，若未收到 ACK，表示有碰撞發生若發生碰撞，必須等候一段隨機的時間，再重新傳送Non-Persistent CSMA(0-persistent CSMA) : 偵測到有其他機器在使用通道，則不再持續偵測，而是隨機等候一段時間後才重新開始偵測每個 frame傳送的平均延遲比 1-persistent要長ㄧ點P-persistent CSMA : 只能用在 slotted通道上若偵測到通道沒有被使用，有 p的機率會立刻送出 frame，(1-p)的機率不會送出，而延遲到下ㄧ個 slot。若發現通道忙碌，則繼續等待到下ㄧ個 slot發生碰撞的處理也是隨機等候一段時間non-persistent CSMA通道使用率比1-persistent CSMA 高，但non-persistent CSMA 傳輸延遲比1-persistent CSMA 大