完全理想化的数据传输所基于的两个假定.ppt

《完全理想化的数据传输所基于的两个假定.ppt》由会员分享，可在线阅读，更多相关《完全理想化的数据传输所基于的两个假定.ppt（39页珍藏版）》请在三一文库上搜索。

1、完全理想化的数据传输所基于 的两个假定 假定 1： 链路是理想的传输信道，所传 送的任何数据既不会出差错也不会丢失 。 假定 2： 不管发方以多快的速率发送数 据，收方总是来得及收下，并及时上交 主机。 这个假定就相当于认为：接收端向主 机交付数据的速率永远不会低于发送端发 送数据的速率。 具有最简单流量控制的数据链 路层协议 现在去掉上述的第二个假定。但是，仍 然保留第一个假定，即主机 A 向主机 B 传输数据的信道仍然是无差错的理想信 道。然而现在不能保证接收端向主机交 付数据的速率永远不低于发送端发送数 据的速率。 由收方控制发方的数据流，乃是计算机 网络中流量控制的一个基本方法。 两种

2、情况的对比（传输均无差错） AB DATA DATA DATA DATA 送主机 B 送主机 B 送主机 B 送主机 B AB DATA 送主机 B DATA 送主机 B 时 间 不需要流量控制需要流量控制 实用的停止等待协议 时 间 AB DATA0 送 主 机 ACK DATA1 送 主 机 ACK (a) 正常情况 AB DATA0 DATA0 送 主 机 ACK (c) 数据帧丢失 重 传 tout 丢 失 ！ AB DATA0 送 主 机 ACK DATA0 丢 弃 ACK (d) 确认帧丢失 重 传 tout丢 失 ！ AB DATA0 NAK DATA0 送 主 机 ACK (b

3、) 数据帧出错 重 传 出错 四种情况 几种常见协议 停止等待协议 连续ARQ协议 选择重传ARQ协议 面向比特的链路控制规程HDLC 停止等待协议的算法 这里不使用否认帧（实用的数据链路层协议大 都是这样的），而且确认帧带有序号 n。 按照习惯的表示法，ACKn 表示“第 n 1 号帧 已经收到，现在期望接收第 n 号帧”。 ACK1 表示“0 号帧已收到，现在期望接收的下 一帧是 1 号帧”； ACK0 表示“1 号帧已收到，现在期望接收的下 一帧是 0 号帧”。 停止等待协议中数据帧和确认帧的 发送时间关系 AB DATA DATA ACK 传播时延 tp 处理时间 tpr 确认帧发送时

4、间 ta 传播时延 tp 处理时间 tpr tT 时间 两个成功发送的 数据帧之间的 最小时间间隔 数据帧的 发送时间 tf 设置的 重传时间 tout 停止等待协议 ARQ 的优缺点 优点：比较简单 。 缺点：通信信道的利用率不高，也就是说，信 道还远远没有被数据比特填满。 为了克服这一缺点，就产生了另外两种协议， 即连续 ARQ 和选择重传 ARQ。这将在后面进 一步讨论。 连续 ARQ 协议的工作原理 DATA0 DATA1 DATA2 DATA3 DATA4 DATA5 重传 DATA2 重传 DATA3 ACK1 ACK2 ACK1 确认 DATA0 ACK2 确认 DATA1 DA

5、TA2 出错，丢弃 DATA3 不按序，丢弃，重传 ACK2 DATA4 不按序，丢弃，重传 ACK2 DATA5 不按序，丢弃，重传 ACK2 ACK3 ACK3 确认 DATA2 ACK4 确认 DATA3 ACK4 重传 DATA5 重传 DATA4 超 时 重 传 时 间 AB tout 送交主机 送交主机 ? ACK2 ACK2 ACK2 需要注意： (1) 接收端只按序接收数据帧。虽然在有差错的 2号帧之 后接着又收到了正确的 3 个数据帧，但接收端都必须将 这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收 到。虽然丢弃了这些不按序的无差错帧，但应重复发送 已发送过的最后一个确

6、认帧（防止确认帧丢失）。 (2) ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1 号 帧；ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。 需要注意： (3) 结点 A 在每发送完一个数据帧时都要设置该帧的超时 计时器。如果在所设置的超时时间内收到确认帧，就立 即将超时计时器清零。但若在所设置的超时时间到了而 未收到确认帧，就要重传相应的数据帧（仍需重新设置 超时计时器）。 在等不到 2 号帧的确认而重传 2 号数据帧时，虽然 结点 A 已经发完了 5 号帧，但仍必须向回走，将 2号帧 及其以后的各帧全部进行重传。连续 ARQ 又称为Go- back

7、-N ARQ，意思是当出现差错必须重传时，要向回 走 N 个帧，然后再开始重传。 需要注意： (4) 以上讲述的仅仅是连续 ARQ 协议的工作原理。协议 在具体实现时还有许多的细节。例如，用一个计时器就 可实现相当于 N 个独立的超时计时器的功能。 发送 网上各站点在任何时刻只要需要，就可以自由地发送信 息（以帧的形式）。 信息发送完毕，发送站等待一段时间，等待时间等于信 道上最远的两个站之间的传输时延的两倍。 若在等待时间内收到接收站的确认信息，则表明发送成 功，否则重发该数据帧。但为了避免继续冲突，各站需 等待一段随机时间后再重发；若再产生冲突，则再等待 一段随机时间再重发 若多次重发都失

8、败（仍收不到确认信息），则停止发送 该帧。 ALOHA协议的最大特点是“想说就说”。 纯ALOHA协议之原理 纯ALOHA协议之原理 接收 接收站根据“帧校验字段”（同HDLC帧）值对所接 收的帧进行差错检验。 如果检验无差错，而且地址相符，接收站就发送一 个确认帧。否则就丢弃所接收的帧。 帧可能因信道噪声或同一时间其他站点传输发出的 帧而损坏 (发生冲突了)。任何帧相遇都会立即产生 冲突（collision） 纯ALOHA协议最大的缺点是最大吞吐率不到理想 值的18% (吞吐率：成功发送的信息数与实际发送的 信息数之比)。 在一定时间间隔中，信道输出了三个信息包 。由图可见，虽然信道中载有7

9、个信息包 ，实际上只有3个信息包成功发射。其平 均通过量为37。 1 U 2 U 3 U 信道 t 重发 重发再重发 重发 碰撞碰撞成功成功成功 时隙ALOHA协议 ALOHA的改进版，1972年由Robert提出，可将吞吐率提 高一倍。 将信道时间分为等长的时间长度,每个长度正好等于一个 帧的传输时间（又称“时隙”或“分槽“）。 所有站点的时钟必须保持同步。 各站只能在时隙的起始时间才能开始发送信息。 这样只 有那些都在同一个时隙开始进行传输的帧才有可能冲突 。 故此可能发生冲突的危险区比ALOHA降低了大约一半 ，在任一帧传输时无其他帧发送的概率约为0.368，即信 道的吞吐率最大可达37

10、%。 S-ALOHA 1 U 信道 重发 重发 重发 再重发 碰撞 碰撞成功成功成功 2 U 3 U l从信道-时间图看，S-ALOHA平均通过量和P-ALOHA是一 样的，均为3/7。 l实际中，若考虑的时限增长，用户增多，其成功率要比 P-ALOHA高。 P-ALOHA 与S-ALOHA对比 a 呼叫量 ALOHA系统的通过量曲线 载波监听多路访问协议 CSMA protocol 纯ALOHA和时隙ALOHA的传输效率都不高，主要原因 是各站独立地决定发送的时刻,使得冲突的概率很高,信道 利用率下降。 CSMA要求各站在发送之前先监听信道上是否有其他站 点正在传送（载波监听）。如果有，就稍

11、候；如果无， 就发送。 如果多个站点同时发送，就会产生冲突，导致信息混淆 ，传输失败。 站点在传输后将等待一定时间（往返时间加上确认帧争 用时间）以接收确认帧。收不到确认(因冲突)就重传。 最大吞吐率远远超过纯ALOHA和时隙ALOHA，取决于 传播时间（媒体长度）和帧的长度：帧越长，传播时间 越短，吞吐率越高。 载波监听多路访问协议CSMA（Carrier Sense Multiple Access Protocols） 载波监听（Carrier Sense） 站点在为发送帧而访问传输信道之前，首先监听信 道有无载波，若有载波，说明已有用户在使用信道 ，则不发送帧以避免冲突。 多路访问（Mu

12、ltiple Access） 多个用户共用一条线路 监听算法 使用CSMA，需要某种算法来规定发现信道忙 时各站点应该采取的策略。 于是就有了几种采用不同载波监听策略的 CSMA技术： 非坚持CSMA 1-坚持CSMA P-坚持CSMA 性能: CSMA 时隙 ALOHA 纯 ALOHA 非坚持CSMA 信道监听信道监听 如果信道忙 ，等待一个随机 时间，然后再次 对信道进行监听 。 如果信道空 闲，刚立即发送 。 发现冲突发现冲突 等待一个随 机时间，然后重 新开始。 1-坚持CSMA 信道监听信道监听 如果信道忙， 继续监听信道，一 旦发现信道空闲， 立即发送。 发现冲突发现冲突 等待一个

13、随机 时间，然后重新开 始。 之所以称为“1-坚持”， 原因是主机一发现信道 空闲，百分之百（即概 率为1）肯定发送。 p-坚持CSMA 信道监听信道监听 如果信道忙，等 待直到信道空闲。 信道空闲，可能 发送(概率为P) ，可 能延迟一个时间单 位再发送 (概率为1- P)。时间单位通常等 于最大传播时延。 发现冲突发现冲突 等待一个随机时 间，然后重新开始 。 非坚持型CSMA（non-persistent CSMA） 优点：减少了冲突的概率； 缺点：增加了信道空闲时间，数据发送延迟增 大； 信道效率比 1-坚持CSMA低，传输延迟比 1-坚 持CSMA大。 原理 若站点有数据发送，先监听

14、信道； 若站点发现信道空闲，则发送； 若信道忙，等待一随机时间，然后重新 开始发送过程； 若产生冲突，等待一随机时间，然后重 新开始发送过程。 1坚持型CSMA（1-persistent CSMA ） 原理 若站点有数据发送，先监听信道； 若站点发现信道空闲，则发送； 若信道忙，则继续监听直至发现信道空 闲，然后完成发送； 若产生冲突，等待一随机时间，然后重 新开始发送过程。 优点：减少了信道空闲时间； 缺点：增加了发生冲突的概率； 广播延迟对协议性能的影响：广播延迟越大， 发生冲突的可能性越大，协议性能越差； 原理 若站点有数据发送，先监听信道； 若站点发现信道空闲，则以概率p发送数 据，以

15、概率q =1- p 延迟至下一个时槽发送。若 下一个时槽仍空闲，重复此过程，直至数据发 出或时槽被其他站点所占用； 若信道忙，则等待下一个时槽，重新开 始发送； 若产生冲突，等待一随机时间，然后重 新开始发送。 五种多路访问协议性能之比较 S表示信道的吞吐量，在t时间内成功发送的平均帧数； G表示网络负载， t时间内总共发送的平均帧数（成功+重法） 五种多路访问协议性能之比较 几种CSMA系统的通过量，皆是随传播 时延的增大而急剧减小，所以 CSMA只 能在小传播时延情况下有效。 虽然，碰撞检测可改善性能，但随着时 延的增大，其效果也将逐渐减弱。 CSMA在有时延存在的情况下，总有碰 撞发生。

16、要消除碰撞，必须进行非竞争的 集中控制。 每个站在发送数据前，先监听信道上有无其他站正在发送信息，若无 ，则发送数据；则有，则暂不发送，退避一段时间后再尝试。 其最大的特点是“先听后说”。 CSMA的监听策略有三种算法： 非坚持 一旦监听到信道忙就不再坚持听下去，延迟一段随机时间后再重新 监听。（信道利用率不高） 1-坚持 监听到信道忙时仍然坚持听下去，直到空闲为止。一旦信道空闲就 发送。如有冲突，等待一随机时间后再监听。（冲突较大） P-坚持 监听到信道忙时仍然坚持听下去，直到空闲为止。当听到信道空闲 时，以概率p发送数据。(p=1时，即为1坚持） p-坚持的主要问题是如何确定一个合适的p

17、值。 轻载时，1坚持CSMA吞吐量特性最好； 重载时，非坚持CSMA吞吐量特性最好，但时间延迟增大 。 小结：CSMA协议 带冲突检测的载波监听多路访问协议 CSMA/CD 引入原因 当两个帧发生冲突时，两个被损坏帧继续传送毫无意义，而 且信道无法被其他站点使用，对于有限的信道来讲，这是很大的 浪费。如果站点边发送边监听，并在监听到冲突之后立即停止发 送，可以提高信道的利用率，因此产生了CSMA/CD。 原理 站点使用CSMA协议进行数据发送； 在发送期间如果检测到冲突，立即终止发送，并发出一个瞬 间干扰信号，使所有的站点都知道发生了冲突； 在发出干扰信号后，等待一段随机时间，再重复上述过程。

18、 载波监听多路访问/冲突检测 CSMA/CD 载波监听 目的：降低冲突次数 如果信道空闲，立即发送 如果信道忙，等待直到信道空闲 冲突检测 目的：降低冲突的影响，使信道在冲突发生 可以尽快恢复使用 一检测到冲突就放弃传输，等待一个随机时 间，然后重新监听。 CSMA/CD执行过程 每站在发送数据前，先监听信道是否空闲；若是，则发 送数据，并继续监听下去，一旦监听到冲突，立即停止 发送，并在短时间内连续向信道发出一串阻塞信号（ JAM）强化冲突，如果信道忙，则暂不发送，退避一随 机时间后再尝试。 CSMA/CD协议在CSMA协议基础上增加了发送期间检 测冲突的功能。其最大特点是“先听后说先听后说

19、, ,边说边听边说边听”。该 协议已被IEEE 802委员会采纳，并以此为依据制定了 IEEE 802.3标准。 CSMA/CD协议同样可分为“非坚持” 、“1-坚持” 和“p-坚 持” 三种。 以太网通常采用非时隙1-坚持CSMA/CD。 CSMA/CD协议的基本思想 CSMA/CD之性能 Performance of CSMA / CD 如果只有一个站点要发送，信道利用率可达100%。 如果有两个或更多个站点要同时发送，线路利用率和吞 吐率就会下降部分带宽被冲突和退避延迟消耗了。实 际上，一条共享10 Mbps 以太网络通常只能提供24 Mbps的吞吐量给所连接的各个站点。 随着网络利用率

20、的增加，特别是如果有许多站点争用时, 可能出现过载情况。此时，网络的吞吐量将急剧下降，信 道容量的大部分被CSMA/CD算法耗费掉，只有极小部分 用于传送有用的数据。为什么一个共享的以太网要求站点 数不得超过1024个，原因就在此。 人们通常以利用率达到40%作为LAN过载的临界值。利用 率较高的LAN将出现高冲突率，传输时间也极可能变化很 大（由于退避）。 使用网桥或交换机将LAN分成两个或更多个冲突域将是 极其有益的。 以太网工作原理：载波监听多路访问 Carrier Sense Multiple Access (CSMA) 一个站点有数据要发送时，要先将其冲突计数器清零，然 后监听电缆，

21、看是否有其他站点的载波(信号)在传送。 “监听”可以通过监测电缆上是否有电流（每个比特大致为 1820 毫安）来实现。每个比特是以10 MHz (快速以太网 为100 MHz）的时钟频率进行曼彻斯特编码后发送的。 如果信道没有空闲，就等待，直到信道空闲。然后还要再 等一个小的“帧间隔”（IFG）时间（最小为9.6微秒）以便 让所有接收站点有时间为下一轮的传输作好准备。 【帧间隔】以太网数据帧之间的最小时间间隔，用于设备 恢复，以便下一帧数据的接收。任何一个以太网帧，则在 传输前都要等待一个帧间隔时间。只有此期间网络持续空 闲，才能开始试发送。帧间隔使网路上的各个设备都有相 同的机会获得发送权。

22、 以太网工作原理： 冲突检测 Collision Detection (CD) CSMA并不能避免两个站点同时发送。如果两个站点都想 发送，而且都监听到信道是空闲的，它们将都认定目前无 人在使用信道。这样就会产生冲突。 每个正在发送数据的站点都继续监听自己的发送过程。如 果发现冲突（如同轴电缆上的电流值超过24毫安），就立 即停止发送，而改发一个32比特的阻塞码。发送阻塞码的 目的是确保各接收方将因CRC差错而丢弃该帧。 带冲突检测的监听算法把浪费带宽的时间减少到检测冲突 的时间。 为保证在帧传输时间内能检测到冲突，要求限制最小帧长( 持续时间应不小于2倍的最大传播时延)。接收站将对小于 最小

23、帧长的帧当作冲突碎片处理而丢弃之。 时隙 Slot Time 为了确保所有站点都能在发送站完成发送前开始 接收到帧，以太网规定了最小帧长（如要求每个帧 有效长度不小于64个字节）。最小帧长与网络跨距 、所用的传输媒体类型以及信号达到LAN的最远端 时需要通过的中继器的数目有关。 所有这些因素定义了一个称为“以太网时隙”的参数 。带宽为10 Mbps 或 100 Mbps的以太网时隙为512 比特（64字节，对10 Mbps以太网为51.2微秒）时 间，带宽为 1000 Mbps的以太网时隙为4096比特（ 512字节）时间。 以太网工作原理： 退避重发 Retransmission Back-

24、Off 在一个繁忙的网络上，如果所有站点在冲突发生后都试 图立即重发，肯定会引起所谓“二次冲突”。所以，要求采 取措施将同时重发的概率降低到最小。以太网技术使用 的是所谓“随机退避时间”，即每个站点选择一个随机数， 乘以时隙时间（即最小帧长时间51.2 微秒）。规定重发 前必须先等这一个随机时间。 退避算法中还规定须对重发次数（N）进行计数，并将最 大重发次数限定为16次，即16次冲突后站点将放弃发送 ，并报告一个错误。 每次重发时,发送站点先构造一个数列: 0, 1, 2, 3, 4, 5, . L ，其中L为2K -1，K=N，K10。然后从该数列中随机 取一个数R。发送站点退避等待（延迟发送）时间为Rx时 隙时间，即 R x 51.2 微秒（对10Mbps以太网）。