2009年6月28日 星期日

多存取協定 ( Multi-access Protocol )

多存取協定 ( Multi-access Protocol )

ALOHA
 
 純 ALOHA ( Pure ALHA )
 ALHA系統基本想法很簡單:使用者只要有資料傳送,就讓資料傳送。當然這樣會發生碰撞,而碰撞的框架(資料框/frame)會損毀。由於廣播回饋的特性,藉由聽取頻道,傳送端一定可以發現傳送的框架是否損毀。
   
 如果使用LAN,回饋會馬上傳回來,使用衛星,則約有 270 msec 的延遲,傳送端才能知道是否成功。框架如果損毀,傳送端須等待一隨機時間,然後再傳送。傳送時間必須是亂數,否則同樣這些框架會一再碰撞。多使用者共享一個頻道,會導致衝突的系統,稱為競爭 ( Contention ) 系統。
  
 槽式ALOHA (Slotted ALOHA )
 為一種可將 ALOHA 容量加倍的方法 ( 1972 Roberts 提出 )。將時間切割為離散式區間,每個區間對應到一個frame。要達到同步的一個方法,就是讓其中一個工作站像時鐘一般,在每個區間發射一個訊號。
Pure ALOHA造成碰撞(collision)的機率極高,為改善網路效能,有人提出slotted ALOHA,將通訊頻道的使用分成一小段時間,約是將一個資料框送上介質的時間,所有的網路節點在時間上必須同步,只有在固定時段上才能傳送資料框,也表示只有在這些時段上才會發生碰撞。
 
 相對於 Pure ALOHA ,Slotted ALOHA 並不需要電腦送出回歸鍵 ( return ),才開始傳送,而是需要等到下一個時槽開始,才能傳送。
 
載子感測多存取 ( Carrier Sense Multiple Access )
   
 機率為1之持續性載子感測多重存取( 1-persistent CSMA ,Carrier Sense Multiple Access )
 當工作站有資料要傳送時,首先監聽頻道上是否有他人在傳輸。如果頻道很忙,則工作站會先等待,直到頻到閒置下來為止。當工作站偵測頻道閒置,則開始傳送框架。如果有碰撞發生,工作站再等待一到隨機時間,然後重新傳送。
 
 此協定之所以稱為機率為1之持續性,是因為只要一發現頻道是閒置時,工作站傳輸的機率為1。
 
 非持續性載子感測多重存取 ( Nonpersistent CSMA )
 在傳送前,工作站首先感應頻道。如果沒有其他人在傳送,則此工作站開始傳送,如果頻道已在使
 用,此工作站並不會為了要抓住前一次傳輸的結束,而持續的感應。相對的,它會等待一個隨機時
 間,然後重覆此演算法。
 
 機率為p之持續性載子感測多重存取( p-persistent CSMA ,Carrier Sense Multiple Access )
 應用於時槽式頻道。當工作站開始準備要傳送時,它會開使感應頻道。如果頻道閒置,則有p的傳送機率,而有q = 1 - p 的機率會延到下一個時槽。如果下一個時槽也是閒置,則可傳輸或再往後延遲,機率仍為p和q。
 
具有碰撞偵測的載子感測多存取
( Carrier Sense Multiple Access with Collision Detection ; CSMA/CD )

原理
在網路上任何一台工作站主機欲與網路上任何一台工作站或伺服器從事資料傳輸時,
該主機要先傾聽 (listen) 網路上是否有其它工作站也在發出要求上網路的信號,如果剛好兩台工作站主機一起同時發出信號,結果勢必產生信號碰撞,此時兩台工作站同時退出上網路爭奪戰,等一段任意時間 (random time) 後再重新發出上網路信號,如果很慶幸此時網路上沒有任何其他信號存在後,該工作站可以傳輸資料至其欲送達之目的地﹔

如果很不幸又發生碰撞或是網路還在從事資料傳輸工作,碰撞事件免不了要發生,因此該工作站仍須等一段任意時間候再嘗試下次機會。這種運作方式稱之為 CSMA/CD。亦即為多重存取/碰撞偵測 (Carrier Sense Multiple Access/Collision Detection, CSMA/CD) 基頻技術傳送封包 (packet)。
當碰撞發生被偵測出來以後,雙方的節點都要送出一個擁塞 (jam) 信號到整個網路,此時網路上所有節點都要停止傳輸動作,並進入等待狀態 (wait state),等待下一個機會。
當兩工作站感應頻道閒置時,而同時開始傳送frame,兩者幾乎可以同時偵測出碰撞。與其讓它傳完整個frame(or packet),卻處處受到干擾,倒不如一旦偵測到碰撞,馬上就停止傳送。很快終止損壞框架的傳輸,可以節省時間以及頻寬。

From WikiPedia
用載波偵聽多路訪問(CSMA)時,所有機器都在 bus 等偵聽通道連接(Multiple Access)。有時儘管偵聽通道已空閒(Carrier Sense:通道的監聽,例如以網卡確定無電壓起伏。),但由於通道傳播遲延的原因,前面已發送的數據尚未到達對方,因此發送的數據仍會發生衝突。 CSMA/CD是對CSMA方式的進一步改進。其原理是在偵聽通道閒置後,在發送數據時網路卡等設備會同時進行衝突檢測。(Collision Detection:當兩個波重疊時會造成電壓異常。)如果在發送數據過程中檢測到衝突,就立即停止發送數據,並在固定時間(一開始是 1 slot times)內等待隨機的時間,再重複發送。若依舊碰撞,則採用 en:truncated binary exponential backoff algorithm,十次之內停止前一次「固定時間」的兩倍時間內隨機再發送,十次後則停止前一次「固定時間」內隨機再發送。嘗試 16 次之後則放棄傳送。

CSMA/CD algorithm:

  • Adapter從network layer取得datagram(資料封包),建立frame。
  • 如果adapter sences(感測)channel(通道)是idle(閒置的),便傳送frame。若是busy,則wait到channel為idle為止,再傳送。
  • 沒有collision,如果該adapter在傳送frame時,沒有其他adapter在傳送(即也在使用channel),則該adapter便完成該frame的傳送。
  • 反之,有collision,有其他adapter在傳送,該adapter便會aborts停止傳送frame,而送出一48 bits的jam signal(擁擠訊號)。
  • 送出jam signal後,該adapter便會進入exponential backoff。第n次collision,adapter便從0~2n-1中隨機選一k值,並wait K*512個bit times,然後再去重新sences(感測)channel(通道)。例:第3次collision,從0,1,2,3,4,5,6,7中隨機選一值。


sources:
http://www.cs.nchu.edu.tw/~fileman/notepad/dc4_2.htm
http://www.scu.edu.tw/~distedu/chap4/section4-11.htm
http://zh.wikipedia.org/wiki/CSMA/CD
http://sls.weco.net/node/10698

沒有留言:

張貼留言