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

完全理想化的数据传输所基于的两个假定,假定 1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定 2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。,具有最简单流量控制的数据链路层协议,现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机 A 向主机 B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。,两种情况的对比（传输均无差错）,A,B,DATA,DATA,DATA,DATA,送主机 B,送主机 B,送主机 B,送主机 B,A,B,DATA,送主机 B,DATA,送主机 B,时间,不需要流量控制,需要流量控制,实用的停止等待协议,时间,A,B,送主机,ACK,送主机,ACK,(a)正常情况,四种情况,几种常见协议,停止等待协议连续ARQ协议选择重传ARQ协议面向比特的链路控制规程HDLC,停止等待协议的算法,这里不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号 n。按照习惯的表示法，ACKn 表示“第 n 1 号帧已经收到，现在期望接收第 n 号帧”。ACK1 表示“0 号帧已收到，现在期望接收的下一帧是 1 号帧”；ACK0 表示“1 号帧已收到，现在期望接收的下一帧是 0 号帧”。,停止等待协议中数据帧和确认帧的发送时间关系,A,B,DATA,DATA,ACK,传播时延 tp,处理时间 tpr,确认帧发送时间 ta,传播时延 tp,处理时间 tpr,时间,两个成功发送的数据帧之间的最小时间间隔,数据帧的发送时间,tf,设置的重传时间,tout,停止等待协议 ARQ 的优缺点,优点：比较简单。缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传 ARQ。这将在后面进一步讨论。,连续 ARQ 协议的工作原理,ACK1 确认 DATA0,ACK2 确认 DATA1,DATA2 出错，丢弃,DATA3 不按序，丢弃，重传 ACK2,DATA4 不按序，丢弃，重传 ACK2,DATA5 不按序，丢弃，重传 ACK2,ACK3 确认 DATA2,ACK4 确认 DATA3,超时重传时间,A,B,tout,送交主机,送交主机,?,需要注意：,(1)接收端只按序接收数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。(2)ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1 号帧；ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。,需要注意：,(3)结点 A 在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走，将 2号帧及其以后的各帧全部进行重传。连续 ARQ 又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。,需要注意：,(4)以上讲述的仅仅是连续 ARQ 协议的工作原理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于 N 个独立的超时计时器的功能。,发送网上各站点在任何时刻只要需要，就可以自由地发送信息（以帧的形式）。信息发送完毕，发送站等待一段时间，等待时间等于信道上最远的两个站之间的传输时延的两倍。若在等待时间内收到接收站的确认信息，则表明发送成功，否则重发该数据帧。但为了避免继续冲突，各站需等待一段随机时间后再重发；若再产生冲突，则再等待一段随机时间再重发若多次重发都失败（仍收不到确认信息），则停止发送该帧。ALOHA协议的最大特点是“想说就说”。,纯ALOHA协议之原理,纯ALOHA协议之原理,接收接收站根据“帧校验字段”（同HDLC帧）值对所接收的帧进行差错检验。如果检验无差错，而且地址相符，接收站就发送一个确认帧。否则就丢弃所接收的帧。帧可能因信道噪声或同一时间其他站点传输发出的帧而损坏(发生冲突了)。任何帧相遇都会立即产生冲突（collision）纯ALOHA协议最大的缺点是最大吞吐率不到理想值的18%(吞吐率：成功发送的信息数与实际发送的信息数之比)。,在一定时间间隔中，信道输出了三个信息包。由图可见，虽然信道中载有7个信息包，实际上只有3个信息包成功发射。其平均通过量为37。,时隙ALOHA协议,ALOHA的改进版，1972年由Robert提出，可将吞吐率提高一倍。将信道时间分为等长的时间长度,每个长度正好等于一个帧的传输时间（又称“时隙”或“分槽“）。所有站点的时钟必须保持同步。各站只能在时隙的起始时间才能开始发送信息。这样只有那些都在同一个时隙开始进行传输的帧才有可能冲突。故此可能发生冲突的危险区比ALOHA降低了大约一半，在任一帧传输时无其他帧发送的概率约为0.368，即信道的吞吐率最大可达37%。,S-ALOHA,从信道-时间图看，S-ALOHA平均通过量和P-ALOHA是一样的，均为3/7。实际中，若考虑的时限增长，用户增多，其成功率要比P-ALOHA高。,P-ALOHA 与S-ALOHA对比,ALOHA系统的通过量曲线,载波监听多路访问协议CSMA protocol,纯ALOHA和时隙ALOHA的传输效率都不高，主要原因是各站独立地决定发送的时刻,使得冲突的概率很高,信道利用率下降。CSMA要求各站在发送之前先监听信道上是否有其他站点正在传送（载波监听）。如果有，就稍候；如果无，就发送。如果多个站点同时发送，就会产生冲突，导致信息混淆，传输失败。站点在传输后将等待一定时间（往返时间加上确认帧争用时间）以接收确认帧。收不到确认(因冲突)就重传。最大吞吐率远远超过纯ALOHA和时隙ALOHA，取决于传播时间（媒体长度）和帧的长度：帧越长，传播时间越短，吞吐率越高。,载波监听多路访问协议CSMA（Carrier Sense Multiple Access Protocols）载波监听（Carrier Sense）站点在为发送帧而访问传输信道之前，首先监听信道有无载波，若有载波，说明已有用户在使用信道，则不发送帧以避免冲突。多路访问（Multiple Access）多个用户共用一条线路,监听算法,使用CSMA，需要某种算法来规定发现信道忙时各站点应该采取的策略。于是就有了几种采用不同载波监听策略的CSMA技术：非坚持CSMA1-坚持CSMAP-坚持CSMA性能:CSMA 时隙 ALOHA 纯 ALOHA,非坚持CSMA,信道监听如果信道忙，等待一个随机时间，然后再次对信道进行监听。如果信道空闲，刚立即发送。发现冲突等待一个随机时间，然后重新开始。,1-坚持CSMA,信道监听如果信道忙，继续监听信道，一旦发现信道空闲，立即发送。发现冲突等待一个随机时间，然后重新开始。之所以称为“1-坚持”，原因是主机一发现信道空闲，百分之百（即概率为1）肯定发送。,p-坚持CSMA,信道监听如果信道忙，等待直到信道空闲。信道空闲，可能发送(概率为P)，可能延迟一个时间单位再发送(概率为1-P)。时间单位通常等于最大传播时延。发现冲突等待一个随机时间，然后重新开始。,非坚持型CSMA（non-persistent CSMA）,优点：减少了冲突的概率；缺点：增加了信道空闲时间，数据发送延迟增大；信道效率比 1-坚持CSMA低，传输延迟比 1-坚持CSMA大。原理若站点有数据发送，先监听信道；若站点发现信道空闲，则发送；若信道忙，等待一随机时间，然后重新开始发送过程；若产生冲突，等待一随机时间，然后重新开始发送过程。,1坚持型CSMA（1-persistent CSMA）,原理若站点有数据发送，先监听信道；若站点发现信道空闲，则发送；若信道忙，则继续监听直至发现信道空闲，然后完成发送；若产生冲突，等待一随机时间，然后重新开始发送过程。优点：减少了信道空闲时间；缺点：增加了发生冲突的概率；广播延迟对协议性能的影响：广播延迟越大，发生冲突的可能性越大，协议性能越差；,原理若站点有数据发送，先监听信道；若站点发现信道空闲，则以概率p发送数据，以概率q=1-p 延迟至下一个时槽发送。若下一个时槽仍空闲，重复此过程，直至数据发出或时槽被其他站点所占用；若信道忙，则等待下一个时槽，重新开始发送；若产生冲突，等待一随机时间，然后重新开始发送。,五种多路访问协议性能之比较,S表示信道的吞吐量，在t时间内成功发送的平均帧数；G表示网络负载，t时间内总共发送的平均帧数（成功+重法）,五种多路访问协议性能之比较,几种CSMA系统的通过量，皆是随传播时延的增大而急剧减小，所以 CSMA只能在小传播时延情况下有效。虽然，碰撞检测可改善性能，但随着时延的增大，其效果也将逐渐减弱。CSMA在有时延存在的情况下，总有碰撞发生。要消除碰撞，必须进行非竞争的集中控制。,每个站在发送数据前，先监听信道上有无其他站正在发送信息，若无，则发送数据；则有，则暂不发送，退避一段时间后再尝试。其最大的特点是“先听后说”。CSMA的监听策略有三种算法：非坚持 一旦监听到信道忙就不再坚持听下去，延迟一段随机时间后再重新监听。（信道利用率不高）1-坚持 监听到信道忙时仍然坚持听下去，直到空闲为止。一旦信道空闲就发送。如有冲突，等待一随机时间后再监听。（冲突较大）P-坚持 监听到信道忙时仍然坚持听下去，直到空闲为止。当听到信道空闲时，以概率p发送数据。(p=1时，即为1坚持）p-坚持的主要问题是如何确定一个合适的p 值。轻载时，1坚持CSMA吞吐量特性最好；重载时，非坚持CSMA吞吐量特性最好，但时间延迟增大。,小结：CSMA协议,带冲突检测的载波监听多路访问协议CSMA/CD,引入原因 当两个帧发生冲突时，两个被损坏帧继续传送毫无意义，而且信道无法被其他站点使用，对于有限的信道来讲，这是很大的浪费。如果站点边发送边监听，并在监听到冲突之后立即停止发送，可以提高信道的利用率，因此产生了CSMA/CD。原理站点使用CSMA协议进行数据发送；在发送期间如果检测到冲突，立即终止发送，并发出一个瞬间干扰信号，使所有的站点都知道发生了冲突；在发出干扰信号后，等待一段随机时间，再重复上述过程。,载波监听多路访问/冲突检测CSMA/CD,载波监听目的：降低冲突次数如果信道空闲，立即发送如果信道忙，等待直到信道空闲冲突检测目的：降低冲突的影响，使信道在冲突发生可以尽快恢复使用一检测到冲突就放弃传输，等待一个随机时间，然后重新监听。,CSMA/CD执行过程,每站在发送数据前，先监听信道是否空闲；若是，则发送数据，并继续监听下去，一旦监听到冲突，立即停止发送，并在短时间内连续向信道发出一串阻塞信号（JAM）强化冲突，如果信道忙，则暂不发送，退避一随机时间后再尝试。CSMA/CD协议在CSMA协议基础上增加了发送期间检测冲突的功能。其最大特点是“先听后说,边说边听”。该协议已被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的吞吐量给所连接的各个站点。随着网络利用率的增加，特别是如果有许多站点争用时,可能出现过载情况。此时，网络的吞吐量将急剧下降，信道容量的大部分被CSMA/CD算法耗费掉，只有极小部分用于传送有用的数据。为什么一个共享的以太网要求站点数不得超过1024个，原因就在此。人们通常以利用率达到40%作为LAN过载的临界值。利用率较高的LAN将出现高冲突率，传输时间也极可能变化很大（由于退避）。使用网桥或交换机将LAN分成两个或更多个冲突域将是极其有益的。,以太网工作原理：载波监听多路访问Carrier Sense Multiple Access(CSMA),一个站点有数据要发送时，要先将其冲突计数器清零，然后监听电缆，看是否有其他站点的载波(信号)在传送。“监听”可以通过监测电缆上是否有电流（每个比特大致为 1820 毫安）来实现。每个比特是以10 MHz(快速以太网为100 MHz）的时钟频率进行曼彻斯特编码后发送的。如果信道没有空闲，就等待，直到信道空闲。然后还要再等一个小的“帧间隔”（IFG）时间（最小为9.6微秒）以便让所有接收站点有时间为下一轮的传输作好准备。【帧间隔】以太网数据帧之间的最小时间间隔，用于设备恢复，以便下一帧数据的接收。任何一个以太网帧，则在传输前都要等待一个帧间隔时间。只有此期间网络持续空闲，才能开始试发送。帧间隔使网路上的各个设备都有相同的机会获得发送权。,以太网工作原理：冲突检测Collision Detection(CD),CSMA并不能避免两个站点同时发送。如果两个站点都想发送，而且都监听到信道是空闲的，它们将都认定目前无人在使用信道。这样就会产生冲突。每个正在发送数据的站点都继续监听自己的发送过程。如果发现冲突（如同轴电缆上的电流值超过24毫安），就立即停止发送，而改发一个32比特的阻塞码。发送阻塞码的目的是确保各接收方将因CRC差错而丢弃该帧。带冲突检测的监听算法把浪费带宽的时间减少到检测冲突的时间。为保证在帧传输时间内能检测到冲突，要求限制最小帧长(持续时间应不小于2倍的最大传播时延)。接收站将对小于最小帧长的帧当作冲突碎片处理而丢弃之。,时隙Slot Time,为了确保所有站点都能在发送站完成发送前开始接收到帧，以太网规定了最小帧长（如要求每个帧有效长度不小于64个字节）。最小帧长与网络跨距、所用的传输媒体类型以及信号达到LAN的最远端时需要通过的中继器的数目有关。所有这些因素定义了一个称为“以太网时隙”的参数。带宽为10 Mbps 或 100 Mbps的以太网时隙为512比特（64字节，对10 Mbps以太网为51.2微秒）时间，带宽为 1000 Mbps的以太网时隙为4096比特（512字节）时间。,以太网工作原理：退避重发Retransmission Back-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以太网）。,