任務量自適應的CSMA/CD退避算法研究

周智洋 阮軍政

(上海航天控制技術研究所， 上海 200233)

任務量自適應的CSMA/CD退避算法研究

周智洋 阮軍政

(上海航天控制技術研究所， 上海 200233)

使用OPNET對總線以太網應用場景進行了仿真，研究了不同負載情況和不同算法下的網絡延遲和吞吐量，并提出了一種根據站點剩余任務量來決定退避窗口大小的CSMA/CD退避算法。通過仿真證明了該算法可以改善在重負載情況下的以太網數據傳輸延時和吞吐量。

CSMA/CD； 退避算法； 任務量自適應

0 引言

以太網作為當前應用最普通的局域網技術，使用CSMA/CD(載波監聽多路訪問及沖突檢測)技術，網中的各個站(節點)都能獨立地決定數據幀的發送與接收,每個站在發送數據幀之前，首先要進行載波監聽，只有介質空閑時，才允許發送幀。這時，如果兩個以上的站同時監聽到介質空閑并發送幀，則會產生沖突現象，這使發送的幀都成為無效幀，發送隨即宣告失敗，然后按照退避算法延時一段時間后，再重新爭用介質，重發送幀。

退避算法又稱為補償算法，它可以為再次嘗試傳輸而創建一個隨機的等待時間，這樣不會出現第2次沖突。目前以太網CSMA協議中常用的退避算法有:非堅持,1-堅持,P-堅持。

(1) 非堅持CSMA：假如介質是空閑的，則發送；假如介質是忙的，等待一段隨機時間，重復第一步；

(2) 1-堅持CSMA：假如介質是空閑的，則發送；假如介質是忙的，繼續監聽，直到介質空閑，立即發送；假如沖突發生，則等待一段隨機時間，重復第一步。

(3) P-堅持CSMA：假如介質是空閑的，則以P概率發送，以(1-P)的概率延遲一個時間單位，時間單位等于最大的傳播延遲時間；假如介質是忙的，繼續監聽，直到介質空閑，重復第一步；假如發送被延遲一個時間單位，則重復第一步。

(4) 可預測P-堅持CSMA：假如介質當前有多個節點需要占用信道，或者已經發生多次沖突，可預測P-堅持CSMA則可根據當前的負荷量來判斷發送數據可能碰撞的可能性。當前沖突次數多，則自動減小P值，否則增大P值。

其中非堅持算法傳輸介質的利用率很低，1-堅持算法在網絡重負載時會因較高的沖突率造成較大傳輸延遲，p-堅持算法的性能介于兩者之間，p值的選擇對網絡性能影響明顯，可預測p-堅持算法就是通過預測網絡負載情況來動態調整p值，以達到更優的網絡性能。

文獻[1]在1-堅持算法的基礎上，添加一個abackoff變量，當上一次嘗試傳輸的次數大于當前的abackoff，則增加退避上限值，若小于當前abackoff，則減少退避上限值，通過自適應改變退避上限值來達到減少網絡延遲的目的，但是并abackoff的取值不夠合理，在重負載情況下對網絡性能改善不明顯。

文獻[2]對P-堅持CSMA協議在航空無線通信自組網中的應用進行了研究，并比對了二進制退避算法和P-堅持算法對網絡性能影響，仿真結果顯示P-堅持算法在業務數據突發高的情況下并不取得更好的效果。

文獻[3]中提出了一種動態P-堅持CSMA協議，通過建立二維馬爾可夫鏈模型，進行理論推導并分析歸一化系統飽和吞吐量的性能，其協議性能受到f(p，i)函數的選擇方案影響較大，如何確定合理的選擇方案是一個有待解決的關鍵問題。

目前對1-堅持和P-堅持等CSMA退避算法的改進研究的方向大多是如何讓CSMA網絡能夠自適應的改變退避策略以便在各種負載情況下都可以取得良好的網絡性能，本文結合1-堅持和可預測P-堅持算法的優勢，提出一種簡潔通用的動態改變最大退避窗口max_backoff值的1-堅持型退避算法，簡稱為任務量自適應退避算法。該算法是讓以太網中各站點根據自身的任務量以及對網絡負載情況的自診斷來決定本地發送數據出現碰撞后應該退避的最大時隙數，以此達到在不影響網絡整體吞吐量的情況下，降低網絡時延，在重負載情況下，也可以實現網絡總延時的收斂。

1 任務量自適應退避算法

任務量自適應退避算法適用于一般CSMA總線式以太網，對網絡參數無特殊要求，但是在多沖突、重負載情況下，效果最為明顯，其核心內容就是目前任務重但之前信道爭用失敗多的站點，擁有更多競爭信道的機會，具體算法實現如下：

(1) 設一站點成功發送一個數據包，則該站點成功發送包參數success_pk++；

(2) 計算發送數據包花費的累計時間參數trans_time，包括沖突退避、重發和網絡傳輸的延時，如果出現發送超時而終止發送的情況，這段超時時間也計入trans_time，如果站點空閑，等待需要發送的數據包的時間不計入trans_time；

(3) 得到上述兩個參數后，在下一次沖突發生時，計算之前成功發送一個數據包需要的平均發送時間參數time_per_pk，此參數即為該站點對網絡負載情況的診斷結果，time_per_pk越大，則網絡越擁擠，反之，則越寬松；

(4) 沖突發生后，站點檢查系統設置的最大容忍延時時隙數，以10M以太網為例，1個時隙約為51.2 μs，網絡良好的情況一般指延時1～50 ms，取其中值25 ms，記為500個時隙；

(5) 同時檢查本站待發送隊列中的數據包數量記為任務量參數buf_store，為方便仿真分析，這里以數據包為單位，并設置數據包的長度為常值，不分段發送，依據實際情況也可以設置算法單位為bit數；

(6) 最后在計算最大退避時隙數時，代入上述各參數，計算方法如下：

/* If this is the first attempt, there */

/* are two possible backoff slots. */

if (attempts == 1)

max_backoff = 2;

/* Otherwise the number of possible slots grows */

/* exponentially until it exceeds a fixed limit. */

else if (attempts <= BACKOFF_LIMIT)

{ time_per_pk=trans_time/success_pk;

num=1-((time_per_pk*buf_store)/(500*SLOT_TIME));

if(num<-1)

{num=-1;}

max_backoff = max_backoff * pow(2,num);

if(max_backoff<2)

{max_backoff=2;} }

/* Obtain a uniformly distributed random integer */

/* between 0 and the backoff limit. */

backoff_slots = op_dist_uniform (max_backoff);

if (backoff_slots == OPC_DBL_INVALID)

{ eth_mac_error ("Unable to choose a number of backoff slots.", OPC_NIL, OPC_NIL); }

/* Set a timer for the end of the backoff interval. */

evh = op_intrpt_schedule_self (op_sim_time () + (int) backoff_slots * SLOT_TIME, 0);

if (op_ev_valid (evh) == OPC_FALSE)

{ eth_mac_error ("Unable to schedule end to backoff interval.", OPC_NIL, OPC_NIL); }

上述代碼表示最大退避時隙數max_backoff的初值為2，每發生一次沖突，則乘上2的num次方，站點按照之前的平均發送時間，計算將剩余數據包全部發送需要的時間，再將需要的時間與系統允許延遲時間的中值進行比較，從而決定num的取值。

下面按照上述參數對任務量自適應算法進行仿真分析。

2 仿真分析

使用OPNET進行網絡仿真分析，為體現任務量自適應算法的優勢，設計了一個多沖突、重負載的10M以太網總線場景，如圖1所示。

圖1 10M以太網總線仿真場景

包括20個站點，數據包產生時間為仿真開始后5 s，仿真時間50 s，所有站點設置Interarrival Time(s)設置為exponential(0.016 6)，一個數據包設為10 000 bit。

先使用1-堅持退避算法進行仿真，結果如圖2所示。

(a) 需傳輸的數據總量曲線

(b) 網絡總吞吐量和延時曲線 圖2 仿真結果

從圖2(a)可知，整個以太網平均每秒產生的數據包個數收斂在1 250個左右，合計12.5 Mbit數據，在這種重負載場景下，使用1-堅持退避算法的結果如圖2(b)所示，網絡吞吐量收斂在8M bit/sec以上，而網絡平均延時則無法收斂，隨著仿真時間的增加不斷放大。

再使用任務量自適應退避算法進行仿真，仿真結果如圖3所示。

圖3 使用任務量自適應退避算法的網絡總吞吐量和延時曲線

可見，在重負載以太網總線應用場景中使用改進后算

法，可以在維持網絡吞吐量的同時，實現網絡平均延時收斂于小于0.01 s的極小值。

然后再設置一個輕負載網絡場景，將站點數減少一半，其余參數保持不變，再次分別仿真1-堅持和改進后算法，結果如圖4所示。

可知在輕負載場景中，改進后算法也可以保持和普通1-堅持算法同樣的效果，并稍微加快網絡延時收斂速度。

上面是以網絡整體吞吐量和實時性為主要指標的仿真，接下來以網絡沖突率為指標來進行比較，使用之前的重負載以太網場景，分別仿真1-堅持和改進后退避算法，比對結果圖5所示。

可知在重負載的網絡環境中，使用了改進后算法的站點為了盡快將積壓的任務量發送出去，逐漸縮短了退避窗口，因而導致了更多的沖突。

為了作出進一步的比對分析，設計了一種完全不使用退避算法的網絡模型，即站點在檢測到沖突以后，延時一個整時隙就進入待發送狀態，如果總線空閑則立刻發送數據，仿真結果，如圖6所示。

網絡平均沖突數和平均延時與任務量自適應退避算法效果相當，但是網絡吞吐量卻只有6M bit/sec，相比任務量自適應算法和1-堅持算法的8M bit/sec下降了25%。

通過上述仿真和比對分析可知，任務量自適應算法就是根據用戶需求設置允許延遲時間來實現重負載工況下網絡沖突、網絡吞吐量與網絡實時性三者之間的平衡，優化網絡性能。

(a) 堅持算法下的輕負載網絡吞吐量和延時曲線

(b) 改進后算法下的輕負載網絡吞吐量和延時曲線 圖4 算法曲線

圖5 堅持退避算法和改進后算法造成的網絡平均沖突數對比

圖6 不使用退避算法的仿真結果曲線

3 總結

本文針對基于CSMA/CD協議的總線以太網，提出了一種改進的任務量自適應的退避算法。在網絡重負載的情況下，這種算法可以在保證最大吞吐量的前提下，根據用戶對實時性的要求來實現網絡總延時的快速收斂，但是相比普通1-堅持退避算法，存在網絡總沖突數增加的缺點，適用于重視網絡傳輸總量和傳輸速度，但單個數據的重要性較低的應用場景。

[1] 張爭.秦拯.CSMA中退避算法的改進與仿真[D]．長沙：湖南大學軟件學院，2011：51-55．

[2] 王白云,鄒星,仇啟明.航空自組網退避算法研究[J].航空電子技術，2015(2)：16-20.

[3] 何偉,南敬昌,潘峰.改進的動態P-堅持CSMA協議[J].計算機工程，2010，36(21):118-120.

[4] 梁華,陳振. 非堅持型CSMA與堅持型CSMA退避算法的性能分析與比較[J]．計算技術與自動化，2006，25(3):51-53.

Task-Adaptived Backoff Algorithm for CSMA/CD Protocol

Zhou Zhiyang,Ruan Junzheng

(1.Shanghai Institute of Spaceflight Control Technology，Shanghai 200233，China)

According to the simulations of bus-ethernet scenarios with OPNET, this paper researches the network latency and throughput in the scenarios with different loads and algorithms. A task-adaptived backoff algorithm is proposed, and the simulations prove it is an effective method to improve the the network latency and throughput in a heavy-load ethernet.

CSMA/CD； Backoff algorithm； Task-adaptived

周智洋(1985-)，男，工學碩士，上海航天803研究所，工程師，研究方向：運載火箭控制系統線路綜合設計。 阮軍政(1985-)，男，工學學士，上海航天803研究所工程師，研究方向：運載火箭控制系統線路綜合設計。

1007-757X(2017)04-0031-04

TP311

A

2016.12.03)