CSMA/CA

避免站點間數據傳輸衝突的演演算法

CSMA/CA(Carrier Sense Multiple Access with Collision Avoid,即帶有衝突避免的載波偵聽多路訪問)是一種數據傳輸是避免各站點之間數據傳輸衝突的演演算法,其特點是發送包的同時不能檢測到通道上有無衝突,只能盡量“避免”。例如,如果計算機A和計算機C同時給計算機B發送一個控制消息,它們將同時到達計算機B,導致衝突的發生。當這種衝突發生時,發送者可以隨機等待一段時間,然後重發控制消息。因為控制消息比數據敏感要短得多,所以發生第二次衝突的可能性也要比傳統乙太網要小很多。最終將有一個控制消息正確到達,然後計算機B發送一個響應消息。通常CSMA/CA利用ACK信號來避免衝突的發生,也就是說,只有當客戶端收到網路上返回的ACK信號后才確認送出的數據已經正確到達目的。

概述


無線區域網標準802.11的MAC802.3協議的MAC非常相似
CSMA/CA的過程
,都是在一個共享媒體之上支持多個用戶共享資源,由發送者在發送數據前先進行網路的可用性檢測。在802.3協議中,是由一種稱為CSMA/CD(Carrier Sense Multiple Access with Collision Detection)的協議來完成調節,這個協議解決了在Ethernet上的各個工作站如何在線纜上進行傳輸的問題,利用它檢測和避免當兩個或兩個以上的網路設備需要進行數據傳送時網路上的衝突。在802.11無線區域網協議中,衝突的檢測存在一定的問題,這個問題稱為"Near/Far"現象,這是由於要檢測衝突,設備必須能夠一邊接受數據信號一邊傳送數據信號,而這在無線系統中是無法辦到的。
鑒於這個差異,在802.11中對CSMA/CD進行了一些調整,採用了新的協議CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)或者DCF(Distributed Coordination Function)。 CSMA/CA利用ACK信號來避免衝突的發生,也就是說,只有當客戶端收到網路上返回的ACK信號后才確認送出的數據已經正確到達目的地址。

工作原理


這種協議實際上就是在發送數據幀之前先對通道進行預約。下面為了方便解釋這種技術的主要原理請大家先看下圖。
CSMA/CA協議中的RTS和CTS幀
CSMA/CA協議中的RTS和CTS幀
① 在圖中,
● 站B、站C、站E在站A 的無線信號復蓋的範圍內。而站D不在其內。
● 站A、站E、站D在站B 的無線信號復蓋的範圍內,但站C不在其內。
② 如果站A要向站B發送數據,那麼,站A在發送數據幀之前,要先向站B發送一個請求發送幀RTS(Request To Send)。在RTS幀中已說明將要發送的數據幀的長度。站B收到RTS幀后就向站A回應一個允許發送幀CTS(Clear To Send)。在CTS幀中也附上A欲發送的數據幀的長度(從RTS幀中將此數據複製到CTS幀中)。站A收到CTS幀后就可發送其數據幀了。現在討論在A和B兩個站附近的一些站將做出什麼反應。
● 對於站C,站C處於站A的無線傳輸範圍內,但不在站B的無線傳輸範圍內。因此站C能夠收聽到站A發送的RTS幀,但經過一小段時間后,站C收聽不到站B發送的CTS幀。這樣,在站A向站B發送數據的同時,站C也可以發送自己的數據而不會幹擾站B接收數據(注意:站C收聽不到站B的信號表明,站B也收聽不到站C的信號)。
● 對於站D,站D收聽不到站A發送的RTS幀,但能收聽到站B發送的CTS幀。因此,站D在收到站B發送的CTS幀后,應在站B隨後接收數據幀的時間內關閉數據發送操作,以避免干擾站B接收自A站發來的數據。
● 對於站E,它能收到RTS幀和CTS幀,因此,站E在站A發送數據幀的整個過程中不能發送數據。
③ 雖然使用RTS和CTS幀會使整個網路的效率有所下降。但這兩種控制幀都很短,它們的長度分別為20和14位元組。而數據幀則最長可達2346位元組,相比之下的開銷並不算大。相反,若不使用這種控制幀,則一旦發生衝突而導致數據幀重發,則浪費的時間就更大。雖然如此,但協議還是設有三種情況供用戶選擇:
● 使用RTS和CTS幀;
● 當數據幀的長度超過某一數值時才使用RTS和CTS幀;
● 不使用RTS和CTS幀。
④ 儘管協議經過了精心設計,但衝突仍然會發生。
例如:站B和站C同時向站A發送RTS幀。這兩個RTS幀發生衝突后,使得站A收不到正確的RTS幀因而站A就不會發送後續的CTS幀。這時,站B和站C像乙太網發生衝突那樣,各自隨機地推遲一段時間后重新發送其RTS幀。推遲時間的演演算法也是使用二進位指數退避。
⑤ 為了盡量減少衝突,802.11標準設計了獨特的MAC子層。
(1)首先檢測通道是否有使用,如果檢測出通道空閑,則等待一段隨機時間后,才送出數據。
(2)接收端如果正確收到此幀,則經過一段時間間隔后,向發送端發送確認幀ACK。
(3)發送端收到ACK幀,確定數據正確傳輸,在經歷一段時間間隔后,會出現一段空閑時間。
CSMA/CA協議的工作流程分為兩個分別是:
1.送出數據前,監聽媒體狀態,等沒有人使用媒體,維持一段時間后,再等待一段隨機的時間后依然沒有人使用,才送出數據。由於每個設備採用的隨機時間不同,所以可以減少衝突的機會。
2.送出數據前,先送一段小小的請求傳送報文(RTS : Request to Send)給目標端,等待目標端回應 CTS: Clear to Send 報文後,才開始傳送。利用RTS-CTS握手(handshake)程序,確保接下來傳送資料時,不會被碰撞。同時由於RTS-CTS封包都很小,讓傳送的無效開銷變小。
CSMA/CA通過這兩種方式來提供無線的共享訪問,這種顯式的ACK機制在處理無線問題時非常有效。然而不管是對於802.11還是802.3來說,這種方式都增加了額外的負擔,所以802.11網路和類似的Ethernet網比較總是在性能上稍遜一籌。

主要差別


CSMA/CD:帶有衝突檢測的載波監聽多路訪問,可以檢測衝突,但無法“避免”
CSMA/CA:帶有衝突避免的載波偵聽多路訪問,發送包的同時不能檢測到通道上有無衝突,只能盡量“避免”;
1.兩者的傳輸介質不同,CSMA/CD用於匯流排式乙太網,而CSMA/CA則用於無線區域網802.11a/b/g/n等等;
2.檢測方式不同,CSMA/CD通過電纜中電壓的變化來檢測,當數據發生碰撞時,電纜中的電壓就會隨著發生變化;而CSMA/CA採用能量檢測(ED)、載波檢測(CS)和能量載波混合檢測三種檢測通道空閑的方式;
3.WLAN中,對某個節點來說,其剛剛發出的信號強度要遠高於來自其他節點的信號強度,也就是說它自己的信號會把其他的信號給復蓋掉;
4.本節點處有衝突並不意味著在接收節點處就有衝突。
綜上,在WLAN中實現CSMA/CD是比較困難的。

產生背景


雖然CSMA/CD協議已成功地應用於有線連接的區域網,但無線區域網不能簡單地搬用CSMA/CD協議。其主要原因是:
第一,CSMA/CD協議要求一個站點在發送本站數據的同時還必須不間斷地檢測通道,以便發現是否有其他的站也在發送數據,這樣才能實現“衝突檢測”的功能。但在無線區域網的設備中要實現這種功能花費過大。
第二,更重要的是,即使能夠實現衝突檢測的功能,且在發送數據報時檢測到通道是空閑的,但是,由於無線電波能夠向所有的方向傳播,且其傳播距離受限,在接收端仍然有可能發生衝突,從而產生隱藏站問題和暴露站問題。
此外,無線通道還由於傳輸條件特殊,造成信號強度的動態範圍非常大。這就使發送站無法使用衝突檢測的方法來確定是否發生了碰撞。
因此,無線區域網不能使用CSMA/CD協議,而是以此為基礎,制定出更適合無線網路共享通道的載波監聽多路訪問/衝突避免CSMA/CA協議。CSMA/CA協議利用ACK信號來避免衝突的發生,也就是說,只有當客戶端收到網路上返回的ACK信號后,才確認送出的數據已經正確到達目的。

工作流程


802.11標準為數據幀定義了不同的通道使用優先順序,使用三種不同的時間參數:短幀間隔SIFS、長幀間隔DIFS和點協同間隔PIFS。SIFS最短,使用它作為等待時延的結點將用最高的通道使用優先順序來發送數據幀。網路中的控制幀以及對所接收數據的確認幀都採用SIFS作為發送之前的等待時延。DIFS最長,所有的數據幀都採用DIFS作為等待時延。PIFS具有中等級別的優先順序,主要作為AP定期向服務區內發送管理幀或探測幀所用的等待時延。
CSMA/CA協議的工作原理如圖一所示,主要工作流程是:
(1)當主機需要發送一個數據幀時,首先檢測通道,在持續檢測到通道空閑達一個DIFS之後,主機發送數據幀。接收主機正確接收到該數據幀,等待一個SIFS后馬上發出對該數據幀的確認。若源站在規定時間內沒有收到確認幀ACK,就必須重傳此幀,直到收到確認為止,或者經過若干次重傳失敗後放棄發送。
(2)當一個站檢測到正在通道中傳送的MAC幀首部的“持續時間”欄位時,就調整自己的網路分配向量NAV。NAV指出了必須經過多少時間才能完成這次傳輸,才能使通道轉入空閑狀態。因此,通道處於忙態,或者是由於物理層的載波監聽檢測到通道忙,或者是由於MAC層的虛擬載波監聽機制指出了通道忙。

分類


CSMA/CA分為兩類,第一類是時分多路復用技術與CSMA/CD相結合的方式;第二類是二次檢測避免衝突方式。下面分別介紹這兩種方式。
第一類避免衝突的工作方式要點如下:每次傳遞結束后,立即把時間劃分成時間片,這些時間片分屬網路中各結點。結點根據時間片的先後發送信息,具有第一個時間片的結點首先發送,發送結束后,按優先權順序把發送權交給具有第二個時間片的結點。輪到某個結點而該結點又無報文可發時,它的時間片就空閑不用。如果在時間片輪迴一周后,所有結點都無報文可發,那麼網路就返回到CSMA/CD方式,這時又按競爭方式獲取通道。通道在CSMA/CD方式下使用一次后,系統又回到時間片方式。在這種可避免衝突的系統中,通常給某些結點以特殊的優先權,使它們總是能在第一個時間片發送信息。如果給它們的時間片沒有使用,則重新在其他結點輪流分配時間片。在這種系統中,結點必須有能力完成時間片的同步,執行分配時間片的演演算法以及CSMA/CD方式的演演算法,因此,實現起來較複雜,價格也較貴。這種方法的優點是效率高。
第二類避免衝突的CSMA/CA技術,稱為二次檢測通道訪問技術。這是一種與第一種方式完全不同的CSMA/CA技術。它由結點在發送信息前對介質進行兩次檢測來避免衝突的發生,其工作方式如下:準備發送信息的結點在發送前偵聽介質一段時間(大約為介質最長傳播延遲時間的2倍),如果在這一段時間內介質為“閑”,則開始準備發送,發送準備的時間較長,約為前一段偵聽時間的2~3倍。準備結束后,真正要將信息發送前,再由結點對介質進行一次迅速短暫的偵聽,若仍為空閑,則可正式發送。如果這時偵聽到介質上有信息傳輸,則馬上停止自己即將開始的發送。按某種演演算法延遲一段隨機時間,然後再重複以上的二次檢測過程,所以這種方式又稱為“二次檢測”法。由於第二次偵聽的時間短,在這麼短暫的時間內有兩個點同時發送信息的可能性很小,因此基本上可以避免衝突。同時,這種方式沒有“邊發邊聽”,而僅僅是“先聽后發”,這樣,用不著“邊聽邊發”的複雜的衝突檢測裝置,降低了成本。這種方法的缺點是,發送后一旦發生衝突,也不中止自己的發送,直到發送完畢才知道錯誤,再重新偵聽、重發。