信道共享技术

• • • •
理想的信道利用率
P71页
纯ALOHA的吞吐量与网络负载的关系
S = G e–2G
Abramson于1970年首次推导出的纯ALOHA吞吐量与负载的计算公式 当G=0.5 S=0.5e-1 = 0.184 。 吞吐量 S 达到极大值。
曲线在G>0.5时呈现负的斜 率。 所以在G>0.5时，属于不稳 定区域。 设定（G’,S’）在G>0.5上的 某一点，假定G增大；根据 曲线，则S减小，吞吐量下 降。 表明成功发送帧的数目在减 少而冲突量增加。 在纯ALOHA系统中，G < 0.5
– 每一个帧在到达缓冲区后，都要等待一段时间后才能发出去。 – 在一个时隙内有2个或2个以上的帧到达后，则在下一个时隙
产生冲突
P73页 时隙ALOHA吞吐量公 式： S = Ge-G 此公式为Robert在 1972年推导出来的。 当G=1时， S=Smax=e-1≈0.368 对于时隙ALOHA，不 稳定区域于G > 1 部 分 •与纯ALOHA协议相比 ，降低了产生冲突的概 率，信道利用率最高为 36.8%。
P72页
4.1.2 时隙ALOHA
– 基本思想：把信道时间分成离散的时间槽，槽长为一个帧所
需的发送时间。每个站点只能在时槽开始时才允许发送。其 他过程与纯ALOHA协议相同。 – 信道效率 冲突危险区是纯ALOHA的一半，所以P0 = e-G，S = Ge-G； – 时隙ALOHA、分槽ALOHA、S-ALOHA
Collision detected
•由于无线电信道是一个公用信道，一个
站发送的信息可以同时被多个站收到，而 每个站又是随机发送的，因此这种系统是 一个随机接入系统。
•夏威夷大学早期研制的系统称为ALOHA，
是Additive Link On-line HAwaii system的缩写，而ALOHA恰好又是夏威夷 方言的“你好”。
计算机网络
李英壮 Lyz@dlut.edu.cn http://people.dlut.edu.cn/~lyz
版权申明
本文内容为大连理工大学网络教育学 院2002级计算机网络[谢希仁主编 第三版]课程讲 义，欢迎大家转载，但禁止使用本材料进 行任何商业性或赢利性活动。 转载时请保留本版权声明。 李英壮 lyz@dlut.edu.cn 大连理工大学网络中心 2004年2月
Comm. Tower
• 争用型网络有两种含义：
• 该模式允许多个节点用简单而灵巧的方法，准确地在 同--个频道上进行传输。 • 使用该频道的站愈多，发生碰撞的机率愈高，从而导 致传输延迟增加和信息流通量降低。 • Norman Abramson发表了一系列有关 ALOHA系统的理论 和应用方面的文章，其中 1970年的一篇文章详细阐述 了计算 ALOHA系统的理论容量的数学模型。现在这个 模型 已以经典的 ALOHA模型而闻名于世，当时它评估 出 ALOHA系统的理论容量达到17%的论效率。在1972年， ALOHA通过同步访问而改进成时隙 ALOHA成组广播系统， 使效率提高一倍多。 • Abramson及其同事的研制成果已成为当前使用的大多 数信息包广播系统(其中包括以太网和多种卫星传输系 统)的基础。1995年3月， Abramson因其在争用型系统 的开创性研究工作而获得 IEEE的 KobayaShi奖。
P69页
•
纯ALOHA即原始ALOHA，即可以工作在无线信道；也可 以工作在总线式网络中。
站1 站2
………
站n-1
站N
• • •
上图中是一个ALOHA系统的工作原理图。每一个站均 可以自由地发送数据帧。 约定：帧的长度用发送该帧的时间表示（设帧的长度 为固定值） 用表示发送该帧所需要的时间T0 。
1
7 4
•
•
当站1发送帧1时，其他的站都没有发送数据，所以站1的发送必定成功。这里不 考虑由信道不良而产生的误码。 但随后站2和站N-1发送的帧2和帧3在时间上重叠了一些。这就是以前提到过的 “冲突”。 冲突的结果是使冲突的双方（有时也可能是多方）所发送的数据都出现差错，因 而都必须进行重发。 但是发生冲突的各站不能马上进行重发，因为这样做就会继续冲突下去。ALOHA 系统采用的重发策略是让各站等待一段随机的时间，然后再进行重发。 如再发生冲突，则再等待一段随机的时间，直到重发成功为止。 图中其余的一些帧的发送情况是帧4发送成功，而帧5和帧6发生冲突
P68页
• • • • •
4.1 随机接入：ALOHA
随机接入的特点是所有的用户都可以根据自己意愿随机地发送信息。 当2个或更多的用户同时都在共享通道上发送信息时，就产生了冲突 （collision）。 冲突又称为碰撞，它导致所有线上的用户的发送失败。 随机接入实际上就是争用协议，获得信道使用权的用户才可以发送信 息。 随机接入最初是在70年代初期在夏威夷大学试验成功的。这是为了使 地理上分散的用户通过无线电来使用中心计算机。
0.4
时隙 ALOHA不 稳定区域 Slotted Aloha
0.3
0.2
S = Ge-G
Pure Aloha
0.5 1.0 1.5 2.0
0.1
G = offered load = Np
时隙 ALOHA(Slot- ALOHA)
Node 1
t
Node 2
t
Node
t
Net
t 冲 突 成 功
时间片（slot）； 随机发送； 冲突（collition）； 后退延迟（backup）： 性能分析：吞吐量S、网络负荷G与分组发送成功概率P; P=0.37
P72页
一个帧重传NR次的平均时间是： D = T0 [1 + R +NR (R + (K + 1)/2)]
冲突重传
(时延最小)
冲突再重传
(时延最大)
t T0 RT0 T1 T0 RT0 KT0 T2 平均重传次数与整数 K 有关 K 小，重传时冲突增大。K 大，将减少重传次数 RT0
K = 5，最好的折中数。此时NR与K关系不大，则得出：G/S= 1 + NR 当网络负载增大时，帧的重传次数将按指数规率增长。
NR = e2G -1
• • • • • • •
实例： ALOHA系统中共有10各站均匀地连接再总线上 站间距是4000km；每100km的传播时延是1ms 最远一个站距离主机4000km，往返时延为80ms 设帧长为1200bit，线路数据率为4800b/s 则：一个帧的发送时间 T0 = 0.25s 令 K=5， S=0.08，则G=0.1;NR=0.25;D=1.75T0=0.44s
本章重点
•
• • •
• •
在实际工作中，经常会遇到多个用户(计算机或终端)要同时与一 个主机相连。若每个用户都用独立的信道与主机相连，则往往要 消耗很多的通信线路资源。因此，只要有可能，就应尽量采用信 道共享技术。从层次上讲，本章所讨论的多点接入技术属于数据 链路层中的媒体接入控制MAC子层中的内容。但本章不讨论具体的 网络细节。 当多个用户共享一个容量为C b/s的信道时，理想情况有： 1、如果只有一个用户接入此信道，则该用户可以得到整个信道的 吞吐量C b/s 2、如果同时有N个用户接入此信道，则每个用户能够得到的平均 吞吐量C/N b/s。当然再一个规定的饿时间内，各用户的平均吞吐 量可能超过此平均值 控制这些用户共享信道的协议时简单、可靠，各用户之间互不干 扰， 且是分布式的协议 在计算机网络中使用的信道共享技术可分为三种，即随即接入、 受控接入和信道复用。
4.1.1 纯ALOHA 1、工作原理
• • •
• •
•
•
ALOHA无线电系统(1968--1972) 以太网的核心思是使用共享的公共传输信道。 共享数据传输信道的思想来源于夏威夷大学。60年代未，该校的Norman Abramson及其同事研制了一个名为 ALOHA系统的无线电网络。这个地面无线电 广播系统是为了把该校位于 Oahu岛上的校园内的IBM360主机与分布在其它岛上 和海洋船舶上的读卡机和终端连接起来而开发的。 该系统的初始速度为4800 bps，最后升级到96O0 bps。 该系统的独特之处在于用“入 境”( inbound)和“出境”(outboundl)无线电信道 作两路数据传输。 出境无线电信道(从主机到远方的岛屿)相当简中明了， 只要把终点地址放在传 输的文电标题，然后由相应的接收站译码。 入境无线电信道(从岛内或船舶发到主机)比较复杂，但很有意思，它是采用一 种随机化的重传方法：副站(岛屿上的站)在操作员敲击 Return键之后发出它的 文电或信息包，然后该站等待主站发回确认文电;如果在一定的时限(200到1500 毫微秒)内，在出境信道上 未返回确认文电，则远方站(副站)会认为两个站在 企图同时传输，因而发生了碰撞冲突，使传输数据受破坏，此刻两个站都将再 次选择一个随机时间，试图重发它们的信息包，这时成功的把握就非常大 这种 类别的网络称谓争用型网络，因为不同的站都在争用相同的信道。
• 理想的随机接入系统的吞吐量 S 的极限值 =1。 • 纯ALOHA理想吞吐量的极大值 = 18.4% 。 • 出于安全可靠考虑，建议纯ALOHA的吞吐量不应该超过10%。 • 在纯ALOHA系统出现之后，又提出了多种改进版本。
ห้องสมุดไป่ตู้
• • • • • • • • • •
假定： 多台异步终端通过多点线路接入到主机上 线路速度 = 4800 b/s 每份报文有60个字符 键盘输入一份报文需要2分钟 每个字符用10bit编码 终端的平均速率=5 b/s 采用纯ALOHA方式通信，取 S=1 则：利用信道容量10%； 信道的总数据率=480 b/s 此系统可以接入的终端数量：480/5=96个
帧的时延
• • • • • • • • • • • • 正常情况： 发送一帧需要经过R倍的T0时间后才能收到ACK 最好状态下，发送一帧的时间是 T0 ×（1+R） 有冲突发生： 设超时定时器重传需经过的时间是R倍的T0 +重传的时延 从决定重传到重传结束所需要的时间时间是 n 倍的T0 n 等于 1 到 k 之间的正整数倍数 发生重传时，最小时间T1最大时间T2: T1 = T0 + RT0 + T0 + RT0 T2 = T0 + RT0 +KT0 + RT0 一个帧重传NR次的平均时间是： D = T0 [1 + R +NR (R + (K + 1)/2)]
• 当吞吐量 S 接近0.18时，纯ALOHA系统性能将明显地恶
纯 ALOHA（P-ALOHA）
Node 1 t
Node 2
t
Node n 冲 突 Net 成 功
t
t
随机发送； 冲突（collition）； 后退延迟（backup）： 性能分析：吞吐量S、网络负荷G与分组发送成功概率P; 1970年Abramson研究的结论 — G = 0.5 P = 0.18
第四章 信道共享技术
4.1 随机接入：ALOHA（理解） 4.1.1 纯ALOHA接入 4.1.2 时隙ALOHA（S-ALOHA） 4.2随机接入：CSMA和CSMA/CD（理解 ） 4.2.1 CSMA的几种类型 4.2.2 CSMA/CD的工作原理 4.3 受控接入（理解） 4.4 信道复用（掌握） 4.4.1 频分复用、时分复用河统计时分复 用 4.4.2 波分复用 4.4.3 码分复用
•
•
• •
P69页
• • • • • •
2、性能分析
成功发送的条件：该帧与该帧前后的两个帧的到达时间间隔大于T0 。 ALOHA参考文献中，两个归一化的参数： 1、吞吐量 S：又称为吞吐率，等于在帧的发送时间T0内成功发送的平均帧数。 0≤S≤1。 S=1属于极限情况。当S=1时，帧一个接着一个连续地发送出去，帧与帧之间没 有空隙。 在稳定的情况下，在时间T0内到达系统的平均着帧数（即输入负载）应等于吞 吐量S。 2、网络负载（offered load）G：从网 络的角度看，G等于在T0内总共发送的平 均帧数。其中包括成功发送的帧和因产 生冲突未发送成功而重新发送的帧。 G≥S，只有在不发送冲突时，G=S。 G≥1时，如G=10，表明在T0时间内网络 中总共发送了10个帧。 在稳定的状态下，吞吐量 S 与网络负载 G 的关系： S = G × P [发送成功]