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

周智洋 阮軍政

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

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

周智洋 阮軍政

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

1 任務量自適應退避算法

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

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

(2) 計算發(fā)送數(shù)據(jù)包花費的累計時間參數(shù)trans_time，包括沖突退避、重發(fā)和網(wǎng)絡傳輸?shù)难訒r，如果出現(xiàn)發(fā)送超時而終止發(fā)送的情況，這段超時時間也計入trans_time，如果站點空閑，等待需要發(fā)送的數(shù)據(jù)包的時間不計入trans_time；

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

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

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

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

/* 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); }

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

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

2 仿真分析

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

圖1 10M以太網(wǎng)總線仿真場景

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

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

(a) 需傳輸?shù)臄?shù)據(jù)總量曲線

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

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

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

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

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

法，可以在維持網(wǎng)絡吞吐量的同時，實現(xiàn)網(wǎng)絡平均延時收斂于小于0.01 s的極小值。

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

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

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

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

為了作出進一步的比對分析，設計了一種完全不使用退避算法的網(wǎng)絡模型，即站點在檢測到?jīng)_突以后，延時一個整時隙就進入待發(fā)送狀態(tài)，如果總線空閑則立刻發(fā)送數(shù)據(jù)，仿真結(jié)果，如圖6所示。

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

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

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

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

圖5 堅持退避算法和改進后算法造成的網(wǎng)絡平均沖突數(shù)對比

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

3 總結(jié)

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

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

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

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

[4] 梁華,陳振. 非堅持型CSMA與堅持型CSMA退避算法的性能分析與比較[J]．計算技術(shù)與自動化，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研究所，工程師，研究方向：運載火箭控制系統(tǒng)線路綜合設計。 阮軍政(1985-)，男，工學學士，上海航天803研究所工程師，研究方向：運載火箭控制系統(tǒng)線路綜合設計。

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

TP311

A

2016.12.03)