電腦網路與連結技術第八章 Fast Ethernet 網路 上一頁    下一頁

8-2 CSMA/CD 協定

內容:

 8-2-1 CSMA/CD 網路簡介

『載波檢測多重存取附碰撞偵測』(Carrier Sense Multiple Access with Collision Detection, CSMA/CD IEEE 802.3 所制定的『媒介存取控制』(Medium Access Control, MAC通訊協定。它的上層必須配合 IEEE 802.2 LLC,而下層可依照不同環境需求結合各種傳輸媒介。圖 8-1 CSMA/CD 網路(一般稱之為 Ethernet 網路)的基本結構,網路拓樸圖為匯流排(Bus)架構,網路基本特性如下:

 

8-1 CSMA/CD 網路基本架構圖

基本上CSMA/CD網路為匯流排架構,傳輸媒介為同軸電纜(Coaxial Cable)。傳輸媒介為網路上所有工作站之間通訊的橋樑,任何一部工作站欲傳送資料給其他工作站,必須將資料廣播到(Broadcasting)傳輸媒介上,而且所有工作站都一定要能收到網路上所廣播的訊息,如果有任何一部工作站無法接收到他人發送的訊息(也許網路太大),則表示網路不正常。

網路上同一時間只允許一部工作站發送訊號,如果有兩部以上同時發送訊號,則它們之間的訊號將會在網路上發生碰撞(Collision),造成錯誤訊息而失效(無法解碼)。發生碰撞時,所有傳送中的工作站必須停止傳送,另找適當時機再重新傳送。因此,每部工作站都必須具有偵測碰撞的功能。

同軸電纜上使用電波來傳遞訊號。電波傳遞到纜線的端點會發生反射的現象,造成反射波和前進波混合,而發生訊號錯誤。為了讓網路不要發生反射波現象,我們必須在網路的兩個端點安裝『終端器』(Terminator,以便吸收前進波而使不致發生反射波的現象。

由上述情況可以看出,網路上任何一處斷線、接觸不良、或終端器脫漏將使整個網路癱瘓。

同軸電纜和工作站之間必須透過『收發器』(Transceiver『收發器電纜』(Transceiver Cable的連接。收發器是電流訊號和電波訊號之間的轉換,其功能是在同軸電纜上發送和接收訊號。收發器電纜是一般雙絞線電纜,用來傳遞電流訊號。

以上是 CSMA/CD 網路的特性,接下來將它的基本規範歸類如下:

傳輸速率:10Mbps(高速 Ethernet 可達 100 Mbps ~ 1 Gbps

訊框格式:IEEE 802.3 CSMA/CD格式 ,最大訊框為 1518 位元組,最小訊框為 64 位元組。

傳輸媒介: 50 歐姆之同軸電纜(Coaxial Cable)、無遮蔽式雙絞線(UTP)或光纖(Optical Fiber)。

網路拓樸圖:匯流排架構、廣播方式傳輸,最大網路範圍 2500 公尺。

不提供保證傳送延遲服務:CSMA/CD 協定為競爭式,沒有優先權傳輸服務。所以不保證工作站是否能在某段時間內取得傳輸媒介的使用權。

頻寬使用不保證公平:工作站的使用頻寬沒有平均分配,由競爭原則取得頻寬使用權。

高負載時頻寬使用率低:高負載時工作站之間碰撞機率提昇,易造成頻寬使用率降低。

較不適合多媒體資訊傳輸:因不保證傳輸延遲時間,而且基本協定規格的速率只有 10 Mbps,所以對即時傳輸的多媒體應用較不適合。

由以上介紹,我們大略可以了解 CSMA/CD 有許多致命的缺點,譬如,頻寬分配不均、容易發生碰撞的現象而影響傳輸效率。但目前新的技術都足以克服這些困難,使傳輸效率和傳輸速率較原來標準完善,也才能使 Ethernet 網路立足於工業界。有關這方面的技術都是我們探討 Ethernet 網路的重點,將會在本章及下一章介紹到。

8-2-2 CSMA/CS 協定運作

CSMA/CD 網路採取廣播方式傳輸,任一工作站不是在傳送資料(發送訊號),就是在接收資料(接收訊號)。網路上同一時間只允許一部工作站傳送資料,其餘則處於接收情況。圖 8-2 表示 CSMA/CD 協定的運作流程圖,可分為傳送資料和接收資料兩部分,以下分別說明之:

(A) 傳送資料流程

(1) 工作站欲傳送資料前,必須聆聽(Listen)網路上有沒有訊號在傳送(Carrier Sense)?如果網路上是安靜的 (Quiet),表示沒有任何工作站在使用,便可開始傳送資料;否則就必須等待,而且繼續聆聽。

(2) 當工作站將資料(訊框)傳送出去後,必須立即將其讀回,判斷是否與其他工作站碰撞(Collision Detection)?如發生碰撞便馬上退回不再傳送,等待某一『隨機時間』(Random Time後再回到 流程 1 繼續聆聽;否則便可繼續傳送。

(3) 資料是否傳送完畢?如完畢便發送介面程式通知 LLC 層;否則回到 流程2 繼續發送。

(4) 如發生碰撞(由訊號改變來判斷是否碰撞),傳送端將送出擾亂訊息(Jamming Signal),告知所有工作站,網路已發生碰撞現象,不要再繼續傳送訊號。如果連續發生16 次以上的碰撞,表示網路或電腦發生嚴重的故障,停止傳送且等待修護人員來修護。

(5) 在網路上可能有多部工作站在載波偵測(Carrier Sense)準備要傳送資料,也有可能在傳送途中與其它工作站的訊號發生碰撞。

(B) 接收資料流程

(1) 工作站如沒有在傳送資料,就在接收狀態下。當它接收完資料,如判斷太短便將其拋棄(可能傳送途中發生碰撞而停止傳送),然後繼續接收資料。否則接下一個 流程 (2)

(2) 由訊框內的目的位址(Destination Address, DA)判斷是否傳送給自己,如果不是傳給自己的就將該訊框拋棄,回到 流程 (1)。如果是,接下一個 流程 (3)

(3) 由訊框中 FCSFrame Check Sequence)欄位的值,以 CRCCycle Redundancy Check)檢查方法,檢查訊框內資料是否發生錯誤。如果已發生錯誤則通知 LLC(由 LLC 要求對方重送該訊框),回到 流程 (1)。如果沒有錯誤則接 流程 (4)

(4) 以訊框中長度(Length)欄位的值,與計算資料欄位內資料長度是否相符。如果不符,則通知 LLC(由 LLC 要求對方重送該訊框);如果相符,則刪除訊框的頭尾,將資料(LLC-PDU)傳給 LLC。回到 流程 (1) 繼續接收資料。

8-2 CSMA/CD 通訊協定流程

8-2-3 延遲等待時間

『載波檢測多重存取』(Carrier Sense Multiple Access, CSMA網路中,同時可能有多部工作站準備傳送資料,它們都會在網路上檢測(Carrier Sense)是否有其他工作站正在傳送資料。如果有一部工作站檢測出網路是空閒時(Quiet),便立即將資料送出,但也有可能與其它工作站同時送出,因此發生碰撞的機率非常大。解決的辦法是,等待一段時間後,如果訊號真的不再出現,再傳送資料,如此可大大降低碰撞的機率。

針對檢測網路是否空閒,以便立即傳送訊息,有三種方法:

1 - 堅持法(1-persistent):工作站檢測出網路是空閒時,立即將資料送出。由圖 8-2 可以看出 CSMA/CD 協定是採用 1- 堅持法。

P 堅持法(P-persistent):工作站檢測出網路是空閒時,將資料送出的機率為 P,其中 0 < P < 1P 的計算必須依照當時網路的負載情形。

0 - 堅持法(0-persistent):工作站檢測出網路是空閒時,立刻退出,不再繼續監聽。等待一段隨機延遲之後再回來檢測,如果網路還是空閒就開始傳送資料;否則回到開始檢測的步驟。

基本上,1 - 堅持法』比較適合負載較輕網路的通訊協定,0 - 堅持法』適合於負載較重的環境,P - 堅持法』是採用兩者的折衷情況。如果於較輕負載環境,使用 0 - 堅持法』,會浪費許多時間在等待;於負載較重的環境,如使用1 - 堅持法』,網路上碰撞的機率較為提高。『P - 堅持法』雖然能取得較平衡狀況下使用,但 P 值的計算必須隨時配合網路上的傳輸狀況,也較為複雜。

CSMA/CD 網路之中,發送訊號者必須隨時讀回資料,以便確認是否有碰撞發生。如果讀回的資料和發送的資料相同(表示傳輸訊號可解碼回原來資料),表示沒有發生碰撞的現象。如果讀回的訊號,無法解碼回原來資料,則表示發送出來的訊號已和其他訊號相重疊,成為另一個訊號,和原來發送的訊號不同,也就無法解碼回原來資料。我們判斷這不明訊號也許是其他電腦所發送的,因此稱為『碰撞』(Collision現象。其實,這不一定是發生碰撞,也許是接線不良,造成訊號損失過度嚴重,以致發送端無法解碼回原來資料,也有可能係因纜線受到外來訊號干擾所造成的。在此我們假設網路情況都非常好,不明訊號皆來自其他工作站。(因此對一個網路管理者而言,網路時常發生碰撞時,必須另外思考有關網路環境的問題)

發送訊號者如果偵測出已發生碰撞,必須放棄正在傳送中的資料,並送出擾亂訊號告知其他電腦目前已發生碰撞,不要繼續發送資料。這時候,每一個發送訊號者必須等待一段時間後再繼續檢測網路是否空閒,回到最起始流程(如圖 8-2)。現在,我們來思考一個問題,如果我們在通訊協定裡規定一個固定等待的時間,這時候所有電腦都等待一個固定時間後再去監聽網路,大家都認為空閒,大家又一起傳送資料,又一起發生碰撞。因此,等待時間不可以被固定,而必須是隨機性的。然而,產生這一個隨機時間又必須考慮到目前網路的情況,如果網路負載很高,該次傳送資料已連續碰撞多次了,則等待的隨機時間就必須久一點;如果從來沒有碰撞過,就可以短一點。如何來產生這『隨機延遲時間』(Random Delay TimeCSMA/CD採用『二元指數後退演算法』(Binary Exponential Backoff Algorithm,簡述如下:

n連續發生碰撞次數 (n <= 16) 。當同一筆訊框連續碰撞超過 16 次,表示目前網路負載過重,或者是網路狀況有問題。此時,工作站必須停止傳送,並報告網路狀況。

kk = MIN (n, 10)MIN 是最小值函數。亦即,若碰撞次數超過 10 次,皆以 10 計算。

rr 是隨機延遲單位。r 介於 0 和(2k -1)之間(0 <= r < = 2k -1)。例如,k = 3,表示於 r = {0, 1, 2, 3, 4, 5, 6, 7}之間隨機(random)取一個數。

tt是延遲單位時間。一般都採用網路上的『時槽時間』(Slot Time。一個時槽表示訊號傳遞到網路上最遠距離的『來回傳遞延遲時間』(Round-Trip Propagation Delay。在 CSMA/CD 的通訊協定裡制定網路最遠距離為 2500 公尺,來回時間是 51.2 us

隨機延遲時間 = r * t。隨機延遲時間等於延遲單位時間的隨機延遲單位的倍數。

例如,當第一次發生碰撞時(n = 1),k = MIN(1, 10) = 1r = {0, 1},因此延遲時間有兩種可能:一種立即傳送(0 * 51.2 us);另一種等待 51.2 us1 * 51.2us)。如果第二次發生碰撞(n = 2),k = MIN(2, 10) = 2r = {0, 1, 2, 3},因此延遲時間變成四種隨機機率(0, 51.2us, 102.4us, 153.6us)。當碰撞超過 10 次時(n >= 10),k = MIN(10, 10) = 10r = {0, 1, 2, …, 210 -1},最高的等待時間是 1023 個時槽(1023 * 51.2us)。

8-2-4 訊框格式

MAC 訊框格式』(MAC-Frame牽涉到實體傳輸媒介存取的技術,它是一組在網路上傳送的連續訊號。而訊框的結構和長短,與網路的存取方法有連帶的關係。CSMA/CD 訊框最長為 1518 位元組最短為 64 位元組。其格式如圖 8-3 所示,其中:

前置訊號(Preamble):7個位元組(1010101~1010)。主要是達成接收端的同步功能(Synchronization)。 當傳送端連續發送前置訊號時,接收端利用訊號內的同步訊號(曼撤斯特編碼技巧)調整本身的時序,使其同步於傳送端。

訊框起始符號(Start Frame Delimiter, SFD):一個位元組 (10101011),表示訊框的開始,也表示前置訊號的結束。

目的地位址(Destination Address, DA):用來註明該訊框欲傳送給目的工作站之 MAC 位址,其長度可以是 2 6 個位元組。

來源位址(Source Address , SA):用來註明這訊框是誰發送的。其長度也可以是2 6 個位元組。

長度(Length, LEN):2 個位元組,紀錄訊息欄內資料(LLC-PDU)的長度。

LLC 資料:此欄位是訊息欄位。就是由邏輯鏈路控制層(LLC)所產生的通訊協定單元(LLC-PDU),最長為 1500 byte

補位(Padding, PAD):如果LLC資料(LLC-PDU)小於 46 個位元組時,填入PAD 內隨意資料(無意義的資料),以補滿訊息 46 位元組。

訊框檢查序列(Frame Check Sequence, FCS):4 個位元組,紀錄該訊框的錯誤檢查碼。

 

8-3 CSMA/CD 訊框格式(備註:Ethernet II 訊框有稍修改)

(A) CSMA/CD 位址格式

雖然 CSMA/CD 的位址格式可以有 2 6 個位元組,但同一網路上只能採用其中一種,不可以混合使用。我們也將這個地址稱為 MAC 位址(MAC-address)。如果使用在 Ethernet 網路上,就稱為Ethernet 位址』(Ethernet Address,採用 6 個位元組)。一般 MAC 位址都建構在網路卡上,但也有些網路卡可隨使用者更改設定。基本上,同一個網路上不可以有重覆的 MAC 位址。但一個區域網路上工作站不會很多,位址相衝的機率非常小。圖 8-4 CSMA/CD 的位址格式,不論是 2 個或 6 個位元組格式,都可區分為下列兩大類:

 

8-4 CSMA/CD 位址格式

(1) 個別位址(Individual Address)(I/G = 0):任何一部工作站的 MAC 位址都是唯一性的,不會與他人衝突。

(2) 群體位址(Group Address)(I/G = 1):代表某一群組的位址。一個群組可包含多部工作站;任何一部工作站也可以屬於多個不同群組。當發送端將 DA 設定為某一群組位址,該群組內所有工作站都可以接收訊框。但 DA 的群組位址又可區分為下列兩種:

多點傳送位址(Multicast Address):表示傳送給某一群組中的所有成員。

廣播位址(Broadcast Address):表示傳送給網路上所有成員,一般都以 DA 欄位內全部是 1 代表廣播位址。

由圖 8-4 48 位元格式的地址,第二個位元(U/L)代表此位址是區域性或廣域性的地址,其意義如下:

(1) 廣域性管理地址(Globally Administered Address)(U/L = 0):表示此地址(個別或群體位址)是廣域性的,可以跨越不同網路之間。當傳送端要將某一個訊框傳送到另一個網路上時,就必須將 DA 內地址設定為廣域性地址。

(2) 區域性管理地址(Local Administered Address)(U/L = 1):表示此地址(個別或群體位址)是區域性的,只能在本地區域網路上使用。

(B) LLC 訊息欄位

在圖 8-3 LLC 訊息欄位可以看出 LLC 層和 CSMA/CD 訊框之間的關係。由 LLC 所建立的 LLC-PDU 之中包含目的服務存取點(DSAP)、來源服務存取點(SSAP)、控制欄和上一層的訊息(網路層)都被 CSMA/CD 當成資料看待。傳送端的 CSMA/CD 通訊軟體將這些資料加上自己的控制訊息後傳送出去;而接收端的 CSMA/CD 則將這些控制訊息去除之後的資料(LLC-PDU)再傳給 LLC 層。

(C) 訊框檢查序列(FCS

四個位元組欄位的 FCS 是作為該訊框的錯誤檢查使用。其所檢查的範圍是從 DA 欄位到 PAD 欄位之間的資料,FCS 錯誤檢查的方法是採用 CRC-32Cyclic Redundancy Check)技巧。CSMA/CD 協定所採用的 CRC-32 多項式 G(x) 如下:

G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x +1

CRC-32 產生器如圖 8-5 所示。(CRC 的工作原理請參考 3-5-3 節介紹)

 

8-5 CRC-32 除法器硬體線路

8-2-5 最小訊框 計算

為了實現 CSMA/CD 網路中碰撞偵測的功能,必須有最小訊框的限制。依照 CSAM/CD 協定規定,工作站之間最遠的距離是 2500 公尺(並非完全相同於網路範圍),在這距離之中也許會包含:電纜、半增益電電纜、AUI 電纜、增益器、及其他所有設備。我們將由最遠兩端之中的一部工作站發送訊號,到達最遠距離的『來回傳遞延遲時間』(Round-Trip Propagation Delay Time,稱之為一個『時槽』(Slot Time。早期預估經歷所有網路設備(網路卡、增益器、收發器)和纜線(同軸電纜、收發器電纜,半增益器電纜)的延遲大約是 46.38 us(微秒)。但為了計算方便及預估不同設備之間的誤差,便將一個時槽設定為 51.2 us

如圖 8-6 所示,工作站 A B 在相隔最遠距離(2500公尺)。又CSMA/CD通訊協定裡,傳送端(A)將訊號發送至網路上,再將其讀回判斷是否發生碰撞。於最差狀態(Worst Case)下,當訊號傳遞到最遠的地方時,剛好另一端工作站(B)發送出訊號,兩個訊號發生碰撞。如果訊號太短,發送端傳送完後,訊號還未到達最遠距離,有可能偵測後,才發生碰撞現象。因此,訊框太短有可能無法偵測碰撞現象,所以我們必須增加訊框長度,讓發送端在訊框傳送完成之前,訊框有足夠的時間到達最遠地方。萬一發生碰撞,發送端才能偵測到碰撞現象。也因此,才有最小訊框的限制。

 

8-6 訊框長度與碰撞偵測

到底最小訊框是多少?我們必須預估最差狀況下,在最遠的地方發生碰撞,而且能將碰撞訊號傳回原來發送端的時間內,此時發送端還在傳送訊框。這一來回的時間剛好是一個時槽(51.2 us)。也就是說,一個訊框傳遞的時間至少要一個時槽時間以上。我們以網路傳送速率 10Mbps 來計算,最小訊框是:

10 × 106 × 51.2 × 10-6 = 512 位元 = 64 位元組。

由圖 8-3 CSMA/CD 的訊框格式中,在整個訊框裡包含著 DASALENFCS LLC-PDUSDF 不計入)。這些總共的長度必須高於 64 為元組,因此我們可以算出最小資料:

64 - 6 (DA) - 6 (SA) - 2 (LEN) - 4 (FCS) = 46 位元組。

如果 LLC-PDU 長度不足 46 位元組,就加入 PAD 欄位的無用的資料,以補足 46 位元。因為 LLC-PDU 的資料長度在 LEN 欄位內有紀錄,所以補上 PAD 欄位並不影響接收端的判斷。

 

翻轉工作室:粘添壽

 

電腦網路與連結技術:

 

 

翻轉電子書系列: