CSMA/CD协议中线性退避算法的改进

刘桂江，施赵媛，彭张节，丁晓贵

（安庆师范大学计算机与信息学院，安徽安庆246133）

CSMA/CD协议中线性退避算法的改进

刘桂江，施赵媛，彭张节，丁晓贵

（安庆师范大学计算机与信息学院，安徽安庆246133）

传统以太网MAC（Media Access Control）子层协议CSMA/CD基于二进制指数退避机制随机选择退避等待时间，随着冲突的增多，随机等待的时间窗口增长过快，造成分组包传输延迟增加较快，网络吞吐量急剧降低。本文对传统以太网中的二进制指数退避机制进行改进，提出一种线性退避的CSMA/CD算法（CSMA/CD-LB）。仿真结果表明，该算法较传统退避算法，能较好提升网络吞吐量和分组传输延迟等网络性能指标。

计算机网络；线性退避算法；仿真；NS2；CSMA/CD

以太网（Ethernet）是现有局域网采用的最为普遍、最为流行的网络协议标准。因此，研究以太网的性能提升方法对计算机网络（尤其是局域网）的发展和应用具有重要意义。在局域网的网络体系结构中，数据链路层被分成逻辑链路控制LLC（Logical Link Control）子层和媒体访问控制MAC（Media Access Control）子层，影响性能的关键层是MAC子层。以太网的MAC子层采用了载波监听多路访问/冲突检测CSMA/CD（Carrier SenseMultiple Access/Collision Detection）的媒体访问机制[1]，协议主要研究局域网中多个节点如何高效访问共享的传输介质。在CSMA/CD协议中，一旦多个节点在访问传输媒体时发生冲突，则调用二进制指数退避算法（Binary Exponential Backoff，BEB）进行处理，可以有效减少这些冲突节点再次冲突的概率[2]，然而该算法会导致“捕获效应（Capture Effect）”[3]。另外，由于冲突的数据会被节点重新发送，造成数据包的传输延迟增大，从而导致网络吞吐量降低。

为了减少这种捕获效应以及提升网络吞吐量，有些学者提出了二进制对数仲裁算法（Binary Logarithmic Arbitration Method，BLAM）[4]，该算法能很好地抑制捕获效应，但对现有以太网硬件改动过大。还有学者提出修改退避上限值的方法[5-7]，这些方法在网络负载较轻时，能较好地抑制捕获效应，但由于退避窗口的选取仍然采用BEB方式，所以在负载较大时，网络吞吐量仍然较低。基于此，本文提出一种改进的CSMA/CD-LB（Linear Backoff）算法，在该算法中，发生冲突的节点再次发送数据之前随机等待的时槽数随冲突次数线性增加，而不是指数增加。这样，可以在不影响公平竞争的前提下，增加冲突节点获取媒体访问权的几率，较好地改善网络吞吐量和分组传输延迟等网络性能指标。

1 CSMA/CD-LB算法

1.1 算法描述

基于CSMA/CD-LB算法的以太网，所有节点在传输数据之前，首先监听共享的媒体，若发现媒体空闲就立即传输数据；若发现媒体忙，则继续监听，直到媒体空闲，然后立即传输数据。传输数据的节点边发送边检测媒体，看是否有冲突产生，一旦监听到媒体上有冲突信号，该节点就向媒体发送一个干扰信号（Jamming），并立即停止数据传输。发送的干扰信号是一个短小的控制信号，其他节点收到干扰信号后，表明媒体上发生了冲突，也都立即停止数据传输，等待随机产生的时间间隙，然后重新进行数据传输[8]。

监听到冲突的节点采用线性退避算法随机选择等待时间。具体实现过程：传输数据的节点若发生了第1次冲突，随机等待0或1个时槽后重新发送数据；若又发生了第2次冲突，它们会从0、1、2中随机选一个时槽数，等待选定的时槽后重新发送数据；若发生了第3次冲突，则它们将从0~3中随机选一个时槽数，等待选定的时槽后再重新发送数据。一般而言，n次冲突后，等待的时槽数从0~n中随机选出，即等待的时槽数随冲突的次数线性增加。传输数据的节点若冲突的次数达到了10次，则等待的最大时槽数固定为10。若冲突的次数达到了16次，节点放弃数据传输，并报告一个错误。

相对于传统的基于CSMA/CD-BEB算法的以太网，CSMA/CD-LB以太网在节点发生冲突后退避等待时间的处理上做了改进。BEB算法中节点在n次冲突后，等待的时槽数从0-2min(n,10)-1（n≤16）中随机选出，即指数增加最大等待时槽数。

1.2 数学分析

算法中的时槽长度为定值slot，则节点在发生i次冲突后等待的时间为

而CSMA/CD-BEB算法中，节点在发生i次冲突后等待的时间为

（1）式和（2）式中的Random函数是随机取值函数。显然TLB-Backoff的平均值比TBEB-Backoff的值要小，表明CSMA/CD-LB算法环境下发生冲突的节点成功获取媒体访问权的概率要大，所以基于CSMA/CD-LB的以太网比基于CSMA/CD-BEB的以太网性能要好一些。

2 NS-2建模

为了比较本文提出的CSMA/CD-LB算法和传统二进制退避算法CSMA/CD-BEB的性能，采用目前学术界广泛使用的网络仿真软件平台NS2[9]（Network Simulator Version 2），对两种退避算法进行仿真。

仿真中，以太局域网由100个节点组成，拓扑结构如图1所示。网络带宽为1Mbps，传播延迟为1ms，网络协议使用CSMA/CD-LB。设定数据传输方向分别为节点0到节点1，节点2到节点3，……，节点98到节点99。节点0和节点1之间的传输层采用UDP协议，并在UDP代理上配置一个CBR流量发生器[10]，其余节点对之间均使用NS2的ftp应用模拟器，用来模拟大批量的数据传送[9]。

图1 以太网拓扑图

3 实验仿真及分析

通过仿真比较基于BEB算法的CSMA/CD和基于LB算法的CSMA/CD传输网络的性能，实验中设定的主要参数如表1所示。

表1 仿真环境参数

实验设定节点0到节点1的CBR通信流采用固定传输速率1Mbps，依次增加通信节点的对数，运行NS源程序，利用AWK工具分析跟踪文件[11-12]，使用gnuplot工具对数据提取结果绘图[11-12]，结果如图2和3所示。

图2网络吞吐量随通信节点对数的变化

图2 表示整个局域网的网络吞吐量随着通信节点对数的增加而变化的情况。由图2可知，两种算法环境下的网络吞吐量都随通信节点对数的增加有降低的趋势，随着通信节点数目的增加，网络吞吐量逐渐趋于稳定，基于BEB算法的网络吞吐量基本稳定在850 Kbps左右，基于LB算法的网络吞吐量基本稳定在890 Kbps左右，较BEB算法，网络吞吐量提升近5%。

图3分组包平均传输延迟随通信节点对数的变化图

图3 为网络分组包平均传输延迟随着通信节点对数的增加而变化的情况。图3结果表明，两种算法环境下的分组包传输延迟都随通信节点对数的增加而增大，在节点数较少时，两种退避算法的网络传输延迟都较低，且相差较小，但在增加到7对通信节点之后，基于LB算法的分组包传输延迟趋于稳定，而基于BEB算法的分组包传输延迟则不断增大。

模拟仿真的结果表明，基于LB的CSMA/CD算法对网络的性能有一定的改善，但丢包的数量也会随着负载的增加而急剧增多。这主要是因为发生冲突的节点随机选择退避等待的时间窗口是线性增加的，较之传统的基于BEB的CSMA/CD算法，冲突节点再次成功发送数据的概率增加，从而提升了网络的吞吐量。

4 结论

以太网采用了基于冲突检测的媒体访问机制，冲突处理算法对网络的性能有较大影响。本文提出的基于线性退避的CSMA/CD算法实现简单，在网络传输性能上较传统的BEB算法有所改善。而系统的丢包率较传统算法略有降低。本文为以太网冲突处理机制的改进提供了一个思路和方法，有利于改善以太网的性能，扩大以太网的应用领域。

[1]Carrier sensemultiple access with collision detection(CSMA/CD) accessmethod and physicallayerspecifications[S].USA:The Institute of Electricaland ElectronicsEngineers,Inc,2005.

[2]党安喜,裴少婧,尚耀东,等.以太网时延仿真与性能分析[J].计算机工程与应用,2009，45（2）：119-121.

[3]马元飞,王顺利.FTP条件下CSMA/CD协议信道访问公平性研究[J].计算机时代，2013（3）：1-3.

[4]MOLLE M L.A new binary logarithmic arbitration method in Ethernet[R].Canada:ComputerSystem Research Institute,1994.

[5]喻莉,冰心,朱光喜.一种新的以太网冲突仲裁算法[J].电子与信息学报，2001，23（10）：1000-1005.

[6]许慧,申东日,陈义俊.新型以太网冲突仲裁算法的设计与仿真[J].计算机仿真，2004，21（11）：113-115.

[7]张争,秦拯.基于OPNET的CSMA/CD改进与仿真[J].现代计算机，2010（2）：98-101.

[8]刘桂江,孙家启,王琦进,等.计算机网络[M].合肥:安徽大学出版社，2008：99-102.

[9]徐雷鸣,庞博,赵耀.NS2与网络模拟[M].北京:人民邮电出版社，2003：3-6，103-104.

[10]黄化吉，冯穗力，秦丽娇，等.NS网络模拟和协议仿真[M].北京：人民邮电出版社，2010：186-187.

[11]曾晓红,胡忠旭,孙骏,等.NS2仿真结果分析方法的研究与实现[J].昆明学院学报，2011，33（6）：56-60.

[12]段绍敏,卢豫开,陈永生.基于NS2的TCP性能仿真研究[J].微计算机信息，2010，26（22）：135-136.

Improve Linear Back off Algorithm in CSMA/CD Protocol

LIU Gui-jiang，SHIZhao-yuan，PENG Zhang-jie，DING Xiao-gui
(School of Computer and Information，Anqing Normal University，Anqing，Anhui 246133，China)

The traditional ethernet MAC sublayer protocol CSMA/CD random ly selects back offwaiting time based on the binary exponential backoff mechanism.As the conflicts increase,random ly waiting time window grows fast,which results in packet transmission delay increases rapidly,and the network throughput decreases sharply.This paper improves the binary exponential back off mechanism in traditional ethernet,and proposes CSMA/CD algorithm based on linear back off.The simulation result shows that the new algorithm can better improve the network throughput and packet transmission delay performance indicators,etc.

computer networks；linear back off algorithm；simulation；NS2；CSMA/CD

TP393.1

A

1007-4260(2016)04-0045-03

时间：2017-1-3 17:19

http://www.cnki.net/kcms/detail/34.1150.N.20170103.1719.013.html

2016-05-18

安徽省教育厅一般科研项目（KJ2013B117），安徽省重点教研项目（2012jyxm354）和安徽省精品资源共享课程（2013gxk067）。

刘桂江，男，安徽怀宁人，硕士，安庆师范大学计算机与信息学院副教授，研究方向为物联网关键技术、下一代互联网、无线通信。E-mail:liuguijiang@163.com

10.13757/j.cnki.cn34-1150/n.2016.04.013