局域网的数据链路层分为逻辑链路层LLC（Logical Link Control）和介质访问控制MAC（Medium Access Control）两个子层，其中，LLC子层负责为网络层提供统一的接口，而MAC子层则负责解决当局域网中因共用信道的使用产生竞争时，如何分配信道使用权的问题。
目前，局域网中广泛采用的介质访问控制协议为CSMA/CD（Carrier Sense Multiple Access with Collision Detection，带冲突检测的CSMA）协议，其基本思想为：当一个站要发送数据时，首先监听信道；如果信道空闲，就发送数据，并继续监听；如果在数据发送过程中监听到了冲突，则立刻停止数据发送，并在等待一段随机的时间之后再重新开始尝试发送数据。如图3.13所示，CSMA/CD的控制过程包含以下四个方面的处理内容：侦听、发送、检测、冲突处理，其中：
◆ 侦听：站点在准备发送帧之前，先通过专门的检测模块侦听总线上是否有数据正在传送（即线路是否忙）。若线路忙，则等待一个延时之后再继续侦听，若仍然忙，则继续延迟等待，一直到线路空闲可以发送数据为止，具体每次等待的延时值由二元指数退避算法（Binary Exponential Back-off）确定；若线路空闲，则向总线上发送数据帧。
图3.13 CSMA/CD的工作流程
其中，二元指数退避算法的工作原理如下：在发生第i次冲突之后，每个站会在0～2i-1之间选择一个随机数，然后等待这么多个时隙（在以太网中每个时隙的长度为51.2 μs），但在达到10次冲突后，随机数将固定在最大值1023（=210−1）上而不再继续增加，并且在第16次冲突之后将放弃发送努力，同时回送一个失败报告给网络层，进一步的失败恢复工作取决于网络层协议。
◆ 发送：当确定要发送之后，通过发送模块向总线发送数据帧。
◆ 检测： 数据帧发送之后也可能还是会发生碰撞冲突，因此，站点要对数据帧一边发送，一边接收，以判断是否发生了冲突（若自己收到的数据帧与原发送的数据帧不一致，则表示发生了冲突）。
◆ 冲突处理：当确认发生冲突之后，则先发送阻塞信息以强化冲突，并立刻停止数据发送，然后再进行侦听工作，以待下次重新发送。
显然，CSMA/CD协议是一种有竞争的介质访问控制协议，该类介质访问控制协议在低负载的链路中具有较好的性能（例如：具有较小的延时），但在高负载的链路中，则无冲突的介质访问控制的性能更佳（例如：具有更高的信道利用率）。目前，代表性的无冲突的介质访问控制协议有基本位图法（Basic Bit-map Method）协议与二进制倒计数（Binary Countdown）协议等。
（1）基本位图法协议：如图3.14所示，基本位图法的工作原理为：假定共享信道上有N个站，则每个竞争周期（称为位图）也恰好分为N个时隙，分别与N个站一一对应。如果一个站有帧要发送，则会在对应自己的那个时隙中插入一个“1”位来声明自己有一帧要发送，因此，当N个时隙都通过了之后，每个站都会知道哪些站有帧要发送，此时，有帧要发送的所有站就可以按照时隙的先后顺序来依次传输数据了。
图3.14 基本位图法协议的工作原理
在上述基本位图法协议中，由于每个站都对哪些站需要发送数据的情况非常清楚，并且遵守统一的规定，所以永远不会发生冲突。当最后一个排队的站发送完帧之后，每个站都可以很容易检测到这个事件，于是，另一个N位的竞争周期又开始了。如果当一个站的位时隙刚刚过去的时候它才做好传送的准备，那么它就非常不幸了，它只有保持沉默，直到每个排队的站都发送完数据，然后新的位图再次到来。像基本位图法协议这样在实际传送数据之前先广播自己有数据要发送的愿望的协议，称为预留协议（Reservation Protocol）。
（2）二进制倒计数协议：基本位图法协议的不足在于每个站均需要1位的位图开销，因此难以扩展到包含有上千个站的大型网络之中。为了解决该问题，人们提出了二进制倒计数协议，其工作原理为：如果一个站想要使用信道，则它首先以二进制位串的形式广播它的地址，并且从高序号的位开始。假定所有地址均具有相同长度，来自不同站的每个地址中的位利用布尔或（OR）在一起，为了避免冲突，对每个站而言，若它看到在自己的地址位中，一个值为0的高序号位被改写成了1，则它将放弃本轮发送。
例如：如果站0010，0100，1001和1010都试图获得信道，则在第一个位时间内，这些站将分别发送0，0，1，1，它们被OR在一起得到1，因此，站0010与0100将选择放弃，而1001与1010则继续第二轮竞争。在第二轮竞争中，由于1001与1010的位均为0，因此继续第三轮竞争。在第三轮竞争中，由于1010的位为1，则1001将选择放弃，最终，1010站获得发送权。而在1010站发送完一帧之后，新一轮的竞争将重新开始。
基于上述方法的协议称为二进制倒计数协议，显然，在该协议中高序站的发送优先级要高于低序站的发送优先级。
由前述分析可知，若能将有竞争协议与无冲突协议的优势结合起来，使得新协议在低负载情况下使用竞争协议，在高负载情况下使用无冲突技术，从而不但可在低负载下获得较短的延迟，同时还可在高负载下获得较高的信道利用率。我们把能满足上述要求的协议称为有限竞争协议（Limited Contention Protocol），其中，自适应树搜索协议就是一种简单有效的有限竞争协议。
自适应树搜索协议的工作原理如下：把网络中的站看作是二叉树的叶子，并根据站点之间的父子关系来将站点分组，如图3.15所示。在一次成功传送之后的第一个竞争时隙，即0号时隙中，所有站点都允许尝试获取信道，若发生了冲突，则在1号时隙中，只有该树中2号节点之下的站才可以参与竞争。若其中之一的站获得了信道，则这一帧之后的那个时隙被保留给节点3下面的那些站。若节点2之下的两个或多个站希望传送数据，则1号时隙将发生冲突，在这种情况下，2号时隙就由节点4下面的站来竞争。
图3.15 包含8个站的二叉树
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
