考研笔记-计算机之计算机网络:数据链路层关键算法“表”述

表-各层协议的关键算法

协议层

协议算法

算法实现

数据链路层

网桥和适配器CSMA/CD算法（以10Mb/s以太网为例）

CSMA/CD协议要点：

1) 组装成帧：

从网络层获得一个分组，加上以太网的首部和尾部，组装成以太网帧，放入适配器的缓存中，等待发送。

2) 载波侦听：即先听后发（持续时长96bit）。

若适配器检测到信道空闲（即在96bit时间内没有检测到信道上有信号），就发送这个帧；若检测到信道忙，则继续检测并等待信道转为空闲（加上96bit时间），然后发送这个帧。

3) 冲突检测：即边听边发（持续时长512bit），冲突停发（持续时长48bit）。

在发送过程中继续检测信道，若一直未检测到碰撞，就顺利将该帧成功发送完毕。若检测到碰撞，则终止数据的发送，并发送人为干扰信号。

4) 指数退避：即随机重发（持续时长r512bit）。

在终止发送后，适配器执行指数退避算法，等待r倍512比特时间后，返回到步骤2)。

指数退避算法：

1) 确定基本退避时间，即争用期2τ。以太网将争用期定为51.2us。对于10Mb/s以太网，在争用期内可发送512bit（先确定争用期，而后才算出10Mb/s的以太网在争用期内发送512bit）。

2) 从离散整数集合{0,1,2，…，(2^k-1)}中随机取出一个数r。重传应退后的时间就是r倍的争用期。参数k=Min{将要重传次数（即冲突碰撞次数），10}。

3) 当重传16次仍不能成功时，则丢弃该帧，并向高层报告。

说明：

1) 冲突检测要求设备在发送数据的同时能够接收数据，并根据信号强度的变化来检测是否发生了冲突；无线网络由于不具有冲突检测的条件，因而使用带冲突避免的载波侦听多点接入，即CSMA/CA

透明网桥的自学习和转发帧算法

1) 先自学习，即登记源MAC地址。

a) 若收到帧的源MAC地址不在转发表中，则在转发表中增加一个项目（[源]MAC地址、[进入]接口、存在时间TTL）；

b) 若收到帧的源MAC地址已在转发表中，则更新MAC地址所在项目的接口和存在时间TTL。

2) 后转发帧，即查找目的MAC地址。

a) 若收到帧的目的MAC地址不在转发表中，则通过除进入接口外的所有其他接口进行转发；

b) 若收到帧的目的MAC地址在转发表中，且目的MAC地址所在项目的接口与收到帧的进入接口不同，则按目的MAC地址所在项目的接口进行转发；

c) 若收到帧的目的MAC地址在转发表中，且目的MAC地址所在项目的接口与收到帧的进入接口相同，则丢弃该帧。

源路由网桥的路由算法

源路由网桥在发送帧时，把详细的路由（由同一局域网中的网桥构成的路由）信息放在帧的首部中。

源点确定路由的算法：

1) 为了发现合适的路由，源站以广播方式向欲通信的目的站发送一个发现帧作为探测之用。

2) 发现帧在整个扩展的以太网中沿着所有可能的路由传送；在传送过程中，每个发现帧都记录所经过的路由（即网桥）；当发现帧到达目的站时，就沿着各自的路由（即网桥）返回源站。

3) 源站在得知这些路由后，从所有可能的路由中选出一个最佳路由。以后凡是从该源站向该目的站发送的帧的首部，都必须携带源站所确定的这一路由信息。

说明：

1) 源路由网桥对主机不是透明的，主机必须知道网桥的标识符以及连接到哪一个网段上；

2) 发现帧还可用于确定整个以太网中可以通过的帧的最大长度；