Aloha 和分段Aloha

在出土之后,两台设备随机选定一个退避时间(最小时间段的0或1倍)。 若又发生了冲突, ..... IEE 802.1 定义了生成树算法用来解决这个问题。 LAN1. LAN2. LAN3. B1.
展开查看详情

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 比特数据浪费了信道。