任务量自适应的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)