信息网络理论22讲义

《信息网络理论22讲义》由会员分享，可在线阅读，更多相关《信息网络理论22讲义（55页珍藏版）》请在金锄头文库上搜索。

1、第2章 点到点传输协议,链路层的差错控制技术 组帧技术 数据链路控制协议及其初始化 网络层和传输层的点对点传输协议,2.1 链路层的差错控制技术,差错检测（奇偶校验码、CRC校验） ARQ协议（等待式ARQ、返回式n-ARQ、选择重传式ARQ、ARPANET并行ARQ） 一段链路达到的最佳效率、所获得的最佳帧长度,2.1.1 差错检测 目的：发现一个传输帧经过物理信道传输后是否正确。 常用的方法：一类是奇偶校验、另一类是CRC循环冗余码校验。 基本思路：发端按照给定的规则在K个信息比特后面增加L个校验比特；接收端对收到的信息比特重新计算L个校验比特，比较接收到的校验比特和本地重新计算的校验比特

2、，如果相同，则认为传输无误，否则，认为传输出错。 1. 奇偶校验码 奇偶校验的种类很多，这里给出K=3，L=4，即输入信息比特为S1，S2，S3校验比特为C1，C2，C3，C4 校验的规则如下表：,如果L=1，,（偶校验）,即为最简单的单比特奇偶校验码，可发现奇数个比特错，但不能发现偶数个比特错。,2. CRC校验,CRC码能检测所有奇数个错误。 当信息比特（K）的长度小于等于2L-1，CRC检测所有的两个错误。 CRC码可以检测长度为L的突发错，码字最小距离为4。 CRC的漏检概率为2-L,2.1.2 ARQ协议 重传（自动请求发端重发） 对于一个重传协议，要从两个方面对其进行评价：一是正确

3、性，二是有效性。 正确性：链路层（DLC）能从接收到的帧中，成功地向网络层输送每一个分组，并且每个分组仅送一次。 有效性（效率）：物理层的比特管道的多少容量被用于必要的传输。被等待和不必要的重传所浪费的容量越少，效率越高。 对物理比特管道作如下的假定： （1）在物理信道上传输的帧到达接收端前被时延了任意可变的时间 （2）帧在传输过程中可能会丢失，也可能出错 （3）帧到达的顺序与发送的顺序相同,1. 等待式ARQ（Stop-and-Wait ARQ） Stop-and-Wait ARQ的基本思想与定时器的设置（溢出） 在ARQ帧中，必须有RN和SN（接收序号和发送序号） 假定A向B发送分组，节点

4、A的发送算法如下： （1）置SN=0 （2）如果从上层接收到一个分组，则将SN指配个该分组，如果没有上层分组则等待 （3）将第SN个分组装入物理帧中发给接收节点B （4）如果从B接收的RNSN，则将SN加1，返回（2）；如果在规定的有限时间内，没有从B接收到RNSN的帧，则返回（3）。,ARQ帧结构,等待式ARQ的工作过程,节点B的接收算法： （1）置RN0 （2）无论何时从A接收到一个SN=RN的分组，将该分组送给上层，并将AN+1 （3）在接收到该分组后的一个规定的有限长时间内，将RN放入一帧的RN域中，发给A，返回（2） 稳妥性：节点B能按照顺序将分组呈现给高层 活动性：不会死循环 假定

5、SN和RN是随时间任意增加的，这样就需要很大的比特域来表示发送序号，但实际上是不需要的，可以采用一个整数的模值（mod N）来表示，如SN mod 8，SN mod 128，也很容易看出，停等式 ARQ SN mod 2就足够了。,2. 返回式nARQ 由于等待式ARQ的效率很低，想要发端在等待对方应答时，应当做更多的事情，提出三种改进方案：返回式nARQ（Go Back n ARQ），选择重复式ARQ（Selective Repeat ARQ），和并行等待式ARQ（ARPANET ARQ）。 返回式nARQ的基本思路：发端没有收到对方应答的情况下，可以连续发送n个分组，收端仅接收正确顺序的分

6、组，其应答中的RN表示RN以前的所有分组都已正确接收。这里的n是一个重要的参数，叫做滑动窗口宽度。 返回nARQ算法的具体描述如下： 设发端使用SNmin表示A目前没有收到应答的分组中序号最小的分组（即发端窗口的低端），SNmax表示它将要从高层接收的分组序号，节点将试图传送SNmin到SNmax1之间的分组。,在序号取m（mod m）的情况下，返回nARQ 的算法如下： 发端（A节点）的算法： （1）置模m的变量SNmin和SNmax等于0 （2）算法从任意顺序重复执行第（3）、（4）、（5）步，但在每步的条件满足时刻到该步被执行的时刻之间的时延是任意的，但该时延是一个有限的值 （3）如果（

7、SNmaxSNmin）mod mn，且上层有个分组到达，则将SNmax指定给该分组，并将SNmax增加至（SNmax+1）mod m （4）如果SNmin不等于SNmax，且当前没有帧在传输，选择一个满足（SNSNmin）mod m（SNmaxSNmin）mod m的SN进行传输，当SNmin 不再改变时，SN的分组的重传间隔应小于一个规定的有限值,收端（B节点）的算法： （1）置模m的变量RN=0，重复执行第（2）和（3）步 （2）当接收到的SN=RN，将分组呈送给高层，并将RN增加至（RN+1）mod m （3）在接收到A的任何一个正确分组后，在一个有限时间内，将收端的RN发给A。 下面讨

8、论返回式nARQ的通过量及最佳帧长,n-ARQ的通过量与最佳帧长,假定帧长是一个固定值，设一帧的传输时间为tf，重传一个数据帧所需要的时间为tT（包括一帧传输时间，处理时间，传输时延和等待应答的时间），一帧正确传输的概率为p，则正确传送一个数据帧所需的平均时间为：, 在发送节点处于饱和状态下，吞吐量的最大值为：,归一化的最大吞吐量为：,在实际中，每一帧数据（ 长为lf比特）通常包含ld比特的数据和lh比特的控制信息，即（lf=ld+lh）。如果帧长较短，控制比特所占用的比例较大，因而信道利用率下降，如果帧长较长，在数据传输过程中，因信道误码的存在而导致帧传输错误的概率较大重传的次数将增大，这也

9、会导致信道利用率的下降，因此存在着一个最佳帧长，使得利用率最高。 设信道的误比特率为pb，在随机错误的信道条件下，数据帧的差错率或误帧率pfr为：,设信道容量为C，则信道真正用于有用信道传输的效率为：,信道利用率与数据长度的关系,当 时，上式可近似地表示为,利用lf=ld+lh，对上式求导，并令其为零，得到最佳数据帧长度ldopt。,3. 选择重发式ARQ 当RN和SN采用模m来表示时，要求m大于等于2n；否则取mn，会引起接收数据序号的混淆。 4. ARPANET ARQ 采用8个并行等待式ARQ，每一个等待式ARQ对应一个虚拟信道，8个虚拟信道分别为AH，输入分组可以任意分配到空闲的虚拟信

10、道AH上。,ARPANET ARQ,2.2 组帧技术,面向字符的组帧技术 面向比特的组帧技术 最佳帧长度,2.2.1 面向字符的组帧技术 传输的基本单元是一个字符（字节），他们都支持数据的透明传输，这些帧结构在处理时非常简单，但缺点是效率较低，插入了许多转换字符，另外数据的长度必须以字节为单位（n整数倍Byte）,SLIP协议的帧格式,PPP的帧格式,用于ARPANET的帧格式,2.2.2 面向比特的组帧技术 通常采用一个特殊的比特称为Flag，如0160（1j表示连续j个“1”）来表示一帧的正常结束，如何解决比特流中连续出现6个“1”，即“0”比特插入技术。,2.2.3 采用长度计数的组帧技

11、术DECNET采用了此方案 组帧技术的关键是正确的表示一帧的何时结束，这里采用了帧长度来指示一帧何时结束，如果最大长度为Kmax，则长度域的比特数至少为： Intlb Kmax + 1 其中 lb = Log2,2.2.4 最佳帧长度 在2.1.3 中讨论的是为了实现最佳的信道效率，在ARQ协议中使用的最佳帧长度ldopt；下面要讨论的是在分组经过多次中转才能到达目的节点时，能使得网络开销最小和时延最小情况下的最佳帧长。,网络开销与时延最小情况下的最佳帧长,一条消息分成不同长度的分组经过中转到达目的节点的过程如图，可以看出，图（b）中分组的传输时延为2倍的分组长度，在图（c）中我们将分组的长度

12、减少一半，则此时的时延仅为原来分组长度的1.5倍。,设消息的长度为M，分组的长度为K，通常每一帧都包含固定的开销V（含头和尾），这样每一条消息要分成 分组， 表示大于或等于x的最小整数。,从降低时延的角度出发，分组应尽可能地小，而帧长K的减小会导致帧数的增加，会引起传输开销增加和网络处理负荷的增加，因此应当增加帧长以降低开销，综合考虑时延和开销两个方面，存在一个最佳帧长。,在以上的讨论中，未讨论打包的时延，只关心消息进入系统后到达目的节点的时延，而对于某些流型业务，将要关心给定的某一个比特进入网络到该比特离开网络的时延，这时必须考虑打包的时延。,可以看出，当链路速率Ci提高后，T主要由K/R决

13、定。,2.3 数据链路控制协议及其初始化,标准的数据链路控制协议 数据链路层协议的初始化,2.3.1 标准的数据链路层协议,IBM提出的SDLC ISO建议的HDLC ANSI规定的ADCCP CCITT（ITU-T）建议的LAPB 其中HDLC与ADCCP功能相同，SDLC是HDLC的功能子集，LAPB是X.25网的DLC协议，也是HDLC的一个子集。 HDLC（ADCCP）是多种链路设计的：多址链路、点对点链路、全双工和半双工链路，它包含有三种模式：NRM，ARM，ABM,标准DLC的帧结构，控制域的格式与DLC的工作过程，为了简化描述，采用以下命令格式： X（Y）Z 其中X表示地址，Y表

14、示信息帧的SN和RN，或监控帧的类型及参数，或无编号帧的类型，Z表示P/F是否置位。,NRM、ABM的工作过程：,2.3.2 数据链路层协议的初始化,链路正常工作时称为UP状态；链路故障时称为DOWN状态，当链路出现故障一段时间后，为保证端到端的可靠传输，网络层和传输层通常采取一定的措施，另选一条新的链路来传输旧链路上未传输的分组，当旧链路恢复工作以后，高层会在该链路中建立一条新的通路来传输新的分组流，因此在一条链路上会出现UP和DOWN交替的情况。,1. 主从模式下链路的初始化，并在HDLC中SNRM对应于上述协议中的INIT，DISC帧对应于上述的DISC，ACK对应于上述的ACKI和AC

15、KD,HDLC的初始化、数据传输及出现的问题,2. 平衡模式中，通信双方是平等的，即A站发送数据时，A是主站，B是从站；当B站发送数据时，B是主站，A是从站，因而相当于两个主从协议在工作。,2.4 网络层和传输层 的点对点传输协议,网络层的点对点传输协议 网际层（互连层）的传输协议IP协议 传输层的点对点传输协议,2.4.1 网络层的点对点传输协议,1. 会话过程（Session）和分组编号 不同的会话过程会共享同一链路 同一个Session中的分组进行标识编号 分组的编号可以采用K个bit，表示一个分组中所含的比特数、字符数或字数（多个字节）组成，采用mod 2K的方式对分组进行循环编号,虚

16、电路中不同会话过程的标识方法,2. 网络层的差错控制 与DLC的差错控制方式类似，采用ARQ方式，但是有所区别： 使用位置不同 分组编号的方式不同 传输顺序的差别 时延不同 采用mod m 的编号方式，则序号为l mod m和（l+m）mod m 的分组在接收端是无法区分的，特别在数据报方式中，任意的时延造成重发拷贝是多余的，因为前一个拷贝潜伏在网络中；在发（l+m）mod m时，有可能l mod m的分组的拷贝先于（l+m）mod m到达，导致接收节点出现不可纠正的错误，尽管可能性会很小。,解决的方法： （1）网络层最好采用虚电路方式； （2）分组的编号的模值应足够大； （3）给每个分组规定一个最大的生存时间，在该区间内，使得分组的序号在使用mod m时不可能出现一个循环。 在TCP协议中，使用（2）、（3）两种方法。,3. 网络层的流量控制 这里讨论如何用于网络层流量控制，当网络发生拥塞或传输时延增加，则应答将被时延，将信源的