Aloha 和分段Aloha

1 .计算机网络 本地局域网络，介质访问控制和以太网。 Dr Sandra I. Woolley Translated by D. Shang

2 .课程内容： 网络种类 广播式网络 介质访问控制 随机媒体访问 ALOHA 协议 分段 ALOHA 协议 （ Slotted ALOHA ） 载波监听多路访问（ CSMA ） 带 冲突检测的载波监听多路访问（ CSMA-CD ） 计划介质 访问 预约 轮询

3 .基本网络类型 交换网络 - 网络通过多路器和转换器直接从数据源到目的地链接。、 广播网络 - 所有的接收端都能收到数据，如局域网。也被称为多路访问网络。

4 .广播式网络 优点 不需要指定地址。 地址相对简单 系统廉价且简约 缺点 不可扩展 如果要避免静态分割（信道），系统需要加入访问控制。 举例 广播通信 卫星通信 移动电话 蓝牙（ 2.4GHz 无线通信） 共轴电缆网络

5 .冲突和介质访问控制（ MAC ） 在广播式网络中，如果不同的传输同时出现并且相互干扰，冲突就会出现。 用来减少和消除冲突，同时有效地分配传输信道的网络协议被称为介质访问控制协议 (MAC). 所有使用同一介质的设备都在同一 广播区域 内。 所有设备的地址都需要符合 MAC 协议，即使机器跟当前传输的信息无关。 介质访问控制主要有两种： 随机访问 - 如同无人主持的会议。冲突可能出现但是协议会进行协调。 Scheduling – 如同有人主持的会议，通信机会轮流分配。

6 .MAC 子层 IEEE 802 数据连接分层包括： MAC 控制子层： 介质协调访问 非连接 的帧传输 服务 识别设备采用 MAC 或物理地址。 带有 MAC 地址的广播帧。 本地连接控制子层 处于网络层和 MAC 控制子层之间。

7 .何为冲突？ 当多个基站同时传输时，冲突就可能发生。同时我们还需考虑传输延时。 即使信道闲置，冲突仍然有可能出现。 为防止冲突， B 必须在 0 到 t prop 时段传输。 最差的情况下，直到 2t prop 时刻 ， A 才能检测到冲突。

8 .设置时间 A 至少要等待 2t prop 时间才能知道通道是否闲置。这段时间被称为 协调时间 。 如果数据的比特率是 R bps ，那么在设置时间中总共使用 2t prop * R 比特，这降低了数据的传输效率。

9 .MAC 延迟 帧传输延迟 从第一位数据传出数据源 MAC 到最后一位数据到达目标 MAC. 吞吐量 通过共享介质的实际传输率。 单位为帧 / 秒或者比特 / 秒。 相关参数 R = 比特率 L = 每帧所含比特数 X = L/R 秒 / 帧 如果站得到一个平均到达率为 l 帧 / 秒 负载 r = l X, 传输数据所到达的比率 最大吞吐量（传输效率 100% ）： R/L 帧 / 秒

10 .连个传输站的效率举例 每帧传输需要 2 t prop 的等待时间。 在 A 站发出数据后， B 站需要等待 t prop R 为传输的比特率 L 每帧所含比特数 标准延迟带宽积 传输延时 传输一帧所用时间

11 .典型 MAC 效率 若 a 远小于 1 ，效率将接近 100% 。 随着 a 接近 1 ，效率逐渐降低。 若一个网络的延迟带宽较大，这个网络就被称为长肥网络（缩写为 LFN ，发音为 ”elephant” ）。根据 RFC 1072 的定义， LFN 网络是带宽 - 延迟积远大于 105bits 网络。 CSMA-CD ( 以太网 ) 协议 : 标准延迟带宽积 传输延迟 传输一帧所用时间

12 .典型延迟带宽积 Distance 10 Mbps 100 Mbps 1 Gbps Network Type 1 m 3.33 x 10 -02 3.33 x 10 -01 3.33 x 10 0 Desk area network 100 m 3.33 x 10 01 3.33 x 10 02 3.33 x 10 03 Local area network 10 km 3.33 x 10 02 3.33 x 10 03 3.33 x 10 04 Metropolitan area network 1000 km 3.33 x 10 04 3.33 x 10 05 3.33 x 10 06 Wide area network 100000 km 3.33 x 10 06 3.33 x 10 07 3.33 x 10 08 Global area network 假设传播速度是 3x10 8 m/s ，下表表明了在单向传输延迟内传输的比特数。 ( 最大以太网帧： 1500 字节 = 12000 比特 )

13 .Load 传输延迟 E[T]/X r r max 1 1 Normalized Delay – Load 曲线 E[T] = 帧的平均传输延时 average frame transfer delay X = 帧的平均传输时间 average frame transmission time 低到达率时，只有帧传输时间。 高到达率时，等待进入信道的时间增加。 最高效率通常小于 100% 。

14 .取决于 t prop R / L 传输延迟 Transfer Delay 负载 Load E[T]/X r r max 1 1 r  max a a  a  > a

15 .随机访问 MAC

16 .随机访问 最简单的形式就是仅仅在需要的时候才传输数据。不等待到网络闲置。 第一个系统是 ALOHA – 由 University of Hawaii 开发用来连接各各岛上的终端。 使用 无线电发射机快速传送数据 - 无设置时间。 通过等待一个响应，发射机可以检测到冲突。如果冲突出现，数据会出现损坏，接收端便会要求重新发送信号。 冲突将导致数据被完全 再传送 。 传输量较低时，冲突的发生几率较小， 再传送不是很频繁。

17 .ALOHA 问题： 冲突至少影响两台设备，它们都需要进行再传送。 如果两台设备马上开始在传送（或者经过相同的延时），冲突仍然会发生而且一直持续直到延时改变。 ALOHA 需要在发生冲突后和进行在传输前随机延时。 因为设备在传输之前不再等待 silence ，延时必须足够长似的一台设备可以完成传输。 在每次冲突发生后，冲突发生的几率都会增加。

18 .Collision Limit Reminder 对于轻负载网络，冲突不经常发生，所有吞吐量很高 随着传输量的增加，更多的冲突发生同时因为冲突损耗的带宽增加。

19 .Collision Dominated 在高负载网络中，冲突发生的几率增加，每个数据包都要发送几次。最终网络变为冲突占优网络，吞吐量降为 0. G 为总负载。 对于 ALOHA, 吞吐量的峰值为信道承载能力的 18.4% 。

20 .分段式 ALOHA 分段式 ALOHA 降低了冲突的几率同时提高了吞吐量。 它规定基站只能在特定的时间分段传输。 每个传输点只能在一个分段的开始处进行传送。每次传送的数据必须少于或者等于一个频道的一个时间分段。 所有的设备共用分段。冲突发生的几率降低因为冲突只会发生在时间分段的开始处，数据传输的途中不会发生冲突。 数据一旦开始传输就不会被打断。

21 .分段式 ALOHA 在低负载网络中相对纯 ALOHA 效果更好。 最高吞吐量是 36.8% 。

22 .ALOHA 的问题 ALOHA Problem 信道带宽因为冲突产生消耗。 通过避免必定会导致冲突的传输，冲突的几率可以被降低。 ALOHA 传输不预先检测信道是否闲着。 载波侦听多路访问（ CSMA ） 可以在传输前监听侦听媒体是否处于空闲状态。

23 .CSMA 基站 A 传输信号，其他站检测信号，并延迟其他的传输 在 t prop 时间后， A 完全占用了信道。 脆弱期 is t= t prop

24 .CSMA 何时停止等待？ 什么是基站停止等待开始传输的条件？ 1- 坚持 CSMA 1-Persistent CSMA 等待直到信道闲置后马上开始传输。如果多余一个传输在等待，那么冲突很有可能发生。 这种‘贪婪’访问机制将造成高冲突发生率。

25 .CSMA – 何时停止等待 非坚持 CSMA 基站检测到信道后就要传输。 如果检测到信道忙碌，另一次检测将被安排。 这种再一次检测的方法叫做退避算法。 如果再一次检测时信道闲着，就马上传输，否则继续安排一次检测。 . 因为基站不坚持检测信道，也不经行在一次检测，冲突便减少。 再检测的缺点效率比 1- 坚持 CSMA 低。因为安排的再检测时间可能比实际需要的长，导致再检测前信道闲置。 .

26 .CSMA – 何时停止等待 ？ P- 坚持 CSMA p-Persistent CSMA P- 坚持 CSMA 是 1- 坚持和非坚持的结合。 基站检测到信道后就准备传输。 如果信道忙碌，基站会持续进行再检测直到信道闲置。 基站马上就开始传输的概率为 p. 基站进行再检测（造成 t prop 的延时）的概率为 1-p. 注意 - 延迟要从信道闲置是开始计，而非坚持方式延迟从第一次检测开始计。

27 .P- 坚持的优点 效率相对较高。检测到信道闲置后马上传输数据的概率是 p 。 P 越高越效率越高。（极限值 p=1 ，就是 1 坚持的情况） 概率 P 可能导致两台设备产生冲突， p 值越低冲突越不易发生。（极限值 p=0 ，就是 0- 坚持或非坚持的情况） 因此 p 的取值需要考虑多方面因素。

28 .CSMA 表现 一般表现为 53% 至 81%- 优于 ALOHA (18% 至 37%). 注意延迟带宽积的影响。（ a=1,0.1 和 0.01 的三种情况） 1- 坚持 非坚持

29 .CSMA 和 ALOHA 的问题 CSMA 和 ALOHA 的冲突都会涉及整个数据包。整个数据包传送之后冲突才能探测到。 比如，一个 1500 比特的数据包，在传输 10 比特后发生冲突，剩下的 1490 比特数据任然会传送但不能正常被接收到。 接受端检测到冲突（通过校验和）之后传送一个否定应答作为响应。之后数据将会重新传输。 显然这样效率很低，剩下的 1490 比特数据浪费了信道。