CSMA/CD是Carrier Sense Multiple Access With Collision Detection的縮寫,含有兩方面的內容,即載波偵聽(CSMA)和衝突檢測(CD)。CSMA/CD訪問控制方式主要用於匯流排型和樹狀網路拓撲結構、基帶傳輸系統。資訊傳輸是以“包”為單位,簡稱信包,發展為IEEE 802.3基帶CSMA/CD區域網標準。
載波監聽多路訪問CSMA的技術也稱做先聽後說LBT(Listen Before Talk)。要傳輸資料的站點首先對媒體上有無載波進行監聽,以確定是否有別的站點在傳輸資料。如果媒體空閒,該站點便可傳輸資料;否則,該站點將避讓一段時間後再做嘗試。這就需要有一種退避演算法來決定避讓的時間,常用的退避演算法有非堅持、1-堅持、P-堅持3種。
計算機區域網一般採用共享介質,這樣可以節約區域網的造價。對於共享介質,關鍵問題是當多個站點要同時訪問介質時,如何進行控制,這就涉及到區域網的介質訪問控制(Medium Access Control,MAC)協議。在網路中伺服器和計算機眾多,每臺裝置隨時都有傳送資料的需求,這就需要有某些方法來控制對傳輸媒體的訪問,以便兩個特定的裝置在需要時可以交換資料。傳輸媒體的訪問控制方式與區域網的拓撲結構、工作過程有密切關係。目前,計算機區域網常用的訪問控制方式有3種,分別是載波多路訪問/衝突檢測(CSMA/CD)、令牌環訪問控制法(Token Ring)和令牌匯流排訪問控制法(Toking Bus)。其中,載波多路訪問/衝突檢測(CSMA/CD)是由ALOHA隨機訪問控制技術發展而來的,在此,對ALOHA隨機訪問控制技術簡要介紹一下。
1.ALOHA協議
ALOHA協議是20世紀70年代在夏威夷大學由Norman Abramson及其同事發明的,目的是為了解決地面無線電廣播通道的爭用問題。ALOHA協議分為純ALOHA和分槽ALOHA兩種。
(1)純ALOHA
ALOHA協議的思想很簡單,只要使用者有資料要傳送,就儘管讓他們傳送。當然,這樣會產生衝突從而造成幀的破壞。但是,由於廣播通道具有反饋性,因此傳送方可以在傳送資料的過程中進行衝突檢測,將接收到的資料與緩衝區的資料進行比較就可以知道資料幀是否遭到破壞。同樣的道理,其他使用者也是按照此過程工作。如果傳送方知道資料幀遭到破壞(檢測到衝突),那麼它可以等待一段隨機長的時間後重發該幀。對於區域網LAN,反饋資訊很快就可以得到;而對於衛星網,傳送方要在270ms後才能確認資料傳送是否成功。透過研究證明,純ALOHA協議的通道利用率最大不超過18%(1/2e)。
(2)分槽ALOHA
1972年,Roberts發明了一種能把通道利用率提高一倍的通道分配策略,即分槽ALOHA協議。其思想是用時鐘來統一使用者的資料傳送。辦法是將時間分為離散的時間片,使用者每次必須等到下一個時間片才能開始傳送資料,從而避免了使用者傳送資料的隨意性,減少了資料產生衝突的可能性,提高了通道的利用率。在分槽ALOHA系統中,計算機並不是在使用者按下回車鍵後就立即傳送資料,而是要等到下一個時間片開始時才傳送。這樣,連續的純ALOHA就變成離散的分槽ALOHA。由於衝突的危險區平均減少為純ALOHA的一半,因此分槽ALOHA的通道利用率可以達到36%(1/e),是純ALOHA協議的兩倍。對於分槽ALOHA,使用者資料的平均傳輸時間要高於純ALOHA系統。
2.載波偵聽多路訪問/衝突檢測(CSMA/CD)
CSMA/CD是Carrier Sense Multiple Access With Collision Detection的縮寫,含有兩方面的內容,即載波偵聽(CSMA)和衝突檢測(CD)。CSMA/CD訪問控制方式主要用於匯流排型和樹狀網路拓撲結構、基帶傳輸系統。資訊傳輸是以“包”為單位,簡稱信包,發展為IEEE 802.3基帶CSMA/CD區域網標準。
(1)CSMA/CD介質訪問控制方案
先聽後發,工作站在每次傳送前,先偵聽匯流排是否空閒,如發現已被佔用,便推遲本次的傳送,僅在匯流排空閒時才傳送資訊。介質的最大利用率取決於幀的長度和傳播時間,與幀長成正比,與傳播時間成反比。
載波監聽多路訪問CSMA的技術也稱做先聽後說LBT(Listen Before Talk)。要傳輸資料的站點首先對媒體上有無載波進行監聽,以確定是否有別的站點在傳輸資料。如果媒體空閒,該站點便可傳輸資料;否則,該站點將避讓一段時間後再做嘗試。這就需要有一種退避演算法來決定避讓的時間,常用的退避演算法有非堅持、1-堅持、P-堅持3種。
① 非堅持演算法。演算法規則如下:
如果媒本是空閒的,則可以立即傳送。
如果媒體是忙的,則等待一個由機率分佈決定的隨機重發延遲後,再重複前一個步驟。
採用隨機的重發延遲時間可以減少衝突發生的可能性。
非堅持演算法的缺點是:即使有幾個著眼點位都有資料要傳送,但由於大家都在延遲等待過程中,致使媒體仍可能處於空閒狀態,使利用率降低。
② 1-堅持演算法。演算法規則如下:
如果媒體是空閒的,則可以立即傳送。
如果媒體是忙的,則繼續監聽,直至檢測到媒體是空閒,立即傳送。
如果有衝突(在一段時間內未收到肯定的回覆),則等待一個隨機量的時間,重複前兩步。
這種演算法的優點是:只要媒體空閒,站點就可立即傳送,避免了媒體利用率的損失。
其缺點是:假若有兩個或兩個以上的站點有資料要傳送,衝突就不可避免。
監聽匯流排,如果媒體是空閒的,則以P的機率傳送,而以(1–P)的機率延遲一個時間單位。一個時間單位通常等於最大傳播時延的2倍。
延遲一個時間單位後,再重複第一步。
如果媒體是忙的,繼續監聽直至媒體空閒並重復第一步。
P-堅持演算法是一種既能像非堅持演算法那樣減少衝突,又能像1-堅持演算法那樣減少媒體空閒時間的折中方案。問題在於如何選擇P的值,這要考慮到避免重負載下系統處於的不穩定狀態。假如媒體忙時,有N個站有資料等待發送,一旦當前的傳送完成,將要試圖傳輸的站的總期望數為NP。如果選擇P過大,使NP>1,表明有多個站點試圖傳送,衝突就不可避免。最壞的情況是,隨著衝突機率的不斷增大,而使吞吐量降低到零。所以必須選擇適當P值使NP<1。當然P值選得過小,則媒體利用率又會大大降低。
(2)二進位制指數退避演算法
重發時間均勻分佈在0~TBEB之間,TBEB=2i–1(2a),a為端-端的傳輸延遲,i為重發次數。該式表明,重發延遲將隨著重發次數的增加而按指數規律迅速地延長。
(3)CSMA/CD
載波監聽多路訪問/衝突檢測方法是提高匯流排利用率的一種CSMA改進方案。該方法為:使各站點在傳送資訊時繼續監聽介質,一旦檢測到衝突,就立即停止傳送,並向匯流排傳送一串阻塞訊號,通知總線上的各站點衝突已發生。
採用CSMA/CD介質訪問控制方法的匯流排型區域網中,每一個結點在利用匯流排傳送資料時,首先要偵聽匯流排的忙、閒狀態。如果總線上已經有資料訊號傳輸,則為匯流排忙;如果總線上沒有資料訊號傳輸,則為匯流排空閒。由於Ethernet的資料訊號是按差分曼徹斯特方法編碼,因此如果總線上存在電平跳變,則判斷為匯流排忙;否則判斷為匯流排空。如果一個結點準備好傳送的資料幀,並且此時匯流排空閒,它就可以啟動傳送。同時也存在著這種可能,那就是在幾乎相同的時刻,有兩個或兩個以上結點發送了資料幀,那麼就會產生衝突,所以結點在傳送資料的同時應該進行衝突檢測。
(4)CSMA/CD方式的主要特點
原理比較簡單,技術上較易實現,網路中各工作站處於同等地位,不要集中控制,但這種方式不能提供優先順序控制,各結點爭用匯流排,不能滿足遠端控制所需要的確定延時和絕對可靠性的要求。此方式效率高,但當負載增大時,傳送資訊的等待時間較長。
3.令牌環(Token Ring)訪問控制
Token Ring是令牌傳輸環(Token Passing Ring)的簡寫。令牌環介質訪問控制方法是透過在環狀網上傳輸令牌的方式來實現對介質的訪問控制。只有當令牌傳輸至環中某站點時,它才能利用環路傳送或接收資訊。當環線上各站點都沒有幀傳送時,令牌標記為01111111,稱為空標記。當一個站點要傳送幀時,需等待令牌透過,並將空標記置換為忙標記01111110,緊跟著令牌,使用者站點把資料幀傳送至環上。由於是忙標記,所以其他站點不能傳送幀,必須等待。
傳送出去的幀將隨令牌沿環路傳輸下去。在迴圈一週又回到原發送站點時,由傳送站點將該幀從環上移去,同時將忙標記換為空標記,令牌傳至後面站點,使之獲得傳送的許可權。傳送站點在從環中移去資料幀的同時還要檢查接收站載入該幀的應答資訊,若為肯定應答,說明發送的幀已被正確接收,完成傳送任務。若為否定應答,說明對方未能正確收到所傳送的幀,原發送站點需要在帶空標記的令牌第二次到來時,重發此幀。採用傳送站從環上收回幀的策略,不僅具有對傳送站點自動應答的功能,而且還具有廣播特性,即可有多個站點接收同一個資料幀。
接收幀的過程與傳送幀不同,當令牌及資料幀透過環上站點時,該站將幀攜帶的目標地址與本站地址相比較。若地址符合,則將該幀複製下來放入接收緩衝器中,待接收站正確接收後,即在該幀上載入肯定應答訊號;若不能正確接收則載入否定應答訊號,之後再將該幀送入環上,讓其繼續向下傳輸。若地址不符合,則簡單地將資料幀重新送入環中。所以當令牌經過某站點而它既不傳送資訊,又無處接收時,會稍經延遲,繼續向前傳輸。
在系統負載較輕時,由於站點需等待令牌到達才能傳送或接收資料,因此效率不高。但若系統負載較重,則各站點可公平共享介質,效率較高。為避免所傳輸資料與標記形式相同而造成混淆,可採用位填入技術,以區別資料和標記。
使用令牌環介質訪問控制方法的網路,需要有維護資料幀和令牌的功能。例如,可能會出現因資料幀未被正確移去而始終在環上傳輸的情況;也可能出現令牌丟失或只允許一個令牌的網路中出現了多個令牌等異常情況。解決這類問題的辦法是在環中設定監控器,對異常情況進行檢測並消除。令牌環網上的各個站點可以設定成不同的優先順序,允許具有較高優先權的站申請獲得下一個令牌權。
歸納起來,在令牌環中主要有下面3種操作。
截獲令牌並且傳送資料幀。如果沒有結點需要傳送資料,令牌就由各個結點沿固定的順序逐個傳遞;如果某個結點需要傳送資料,它要等待令牌的到來,當空閒令牌傳到這個結點時,該結點修改令牌幀中的標誌,使其變為“忙”的狀態,然後去掉令牌的尾部,加上資料,成為資料幀,傳送到下一個結點。
取消資料幀並且重發令牌。由於環網在物理上是個閉環,一個幀可能在環中不停地流動,所以必須清除。當資料幀透過閉環重新傳到傳送結點時,傳送結點不再轉發,而是檢查傳送是否成功。如果發現數據幀沒有被複制(傳輸失敗),則重發該資料幀;如果發現傳輸成功,則清除該資料幀,並且產生一個新的空閒令牌傳送到環上。
4.令牌匯流排訪問控制法(Token Bus)
Token Bus是令牌通行匯流排(Token Passing bus)的簡寫。這種方式主要用於匯流排型或樹狀網路結構中。1976年美國Data Point公司研製成功的ARCnet(Attached Resource Computer)網路,它綜合了令牌傳遞方式和匯流排網路的優點,在物理匯流排結構中實現令牌傳遞控制方法,從而構成一個邏輯環路。此方式也是目前微機局域中的主流介質訪問控制方式。
ARCnet網路把匯流排或樹狀傳輸介質上的各工作站形成一個邏輯上的環,即將各工作站置於一個順序的序列內(例如可按照介面地址的大小排列)。方法可以是在每個站點中設一個網路結點標識暫存器NID,初始地址為本站點地址。網路工作前,要對系統初始化,以形成邏輯環路,其過程主要是:網中最大站號n開始向其後繼站傳送“令牌”信包,目的站號為n+1,若在規定時間內收到肯定的訊號ACK,則n+1站連入環路,否則在n+1繼續向下詢問(該網中最大站號為n=255,n+1後變為0,然後1、2、3、…遞增),凡是給予肯定回答的站都可連入環路並將給予肯定回答的後繼站號放入本站的NID中,從而形成一個封閉邏輯環路,經過一遍輪詢過程,網路各站標識暫存器NID中存放的都是其相鄰的下游站地址。
邏輯環形成後,令牌的邏輯中的控制方法類似於Token Ring。在Token Bus中,資訊是按雙向傳送的,每個站點都可以“聽到”其他站點發出的資訊,所以令牌傳遞時都要加上目的地址,明確指出下一個將到控制的站點。這種方式與CSMA/CD方式的不同在於除了當時得到令牌的工作站之外,所有的工作站只收不發,只有收到令牌後才能開始傳送,所以拓撲結構雖是匯流排型但可以避免衝突。
Token Bus方式的最大優點是具有極好的吞吐能力,且吞吐量隨資料傳輸速率的增高而增加,並隨介質的飽和而穩定下來但並不下降;各工作站不需要檢測衝突,故訊號電壓容許較大的動態範圍,聯網距離較遠;有一定實時性,在工業控制中得到了廣泛應用,如MAP網就是用的寬頻令牌匯流排。其主要缺點在於其複雜性和時間開銷較大,工作站可能必須等待多次無效的令牌傳送後才能獲得令牌。
應該指出,ARCnet網實際上採用稱為集中器的硬體聯網,物理拓撲上有星狀和匯流排型兩種連線方式。