《(精品)网络第3章2.ppt》由会员分享，可在线阅读，更多相关《(精品)网络第3章2.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、流量控制：流量控制：1512233445帧传输模型帧传输模型Time三、三、流量控制流量控制用来确保发送实体发出的数据不会覆盖接收实用来确保发送实体发出的数据不会覆盖接收实体已收数据的一种技术。体已收数据的一种技术。源源实实体体发发送送一一个个PDU，目目标标实实体体收收到到后后发发回回一一个个对对该该PDU的的确认，表示同意接受下一个确认，表示同意接受下一个PDU；源实体必须等待，直到收到确认后才能发送下一个源实体必须等待，直到收到确认后才能发送下一个PDU。1.停停等流量控制等流量控制支持有确认无连接支持有确认无连接LLC服服务的最简单流控形式。务的最简单流控形式。工作原理工作原理目标实体
2、能简单地用停止发送确认的方式来阻止数据流。目标实体能简单地用停止发送确认的方式来阻止数据流。适用于单工和半双工通信。适用于单工和半双工通信。优点与缺点优点与缺点控制简单控制简单适用于当报文被分成适用于当报文被分成不多个较大不多个较大PDU发送发送时。时。当一个报文用多个当一个报文用多个PDU发送发送;链路的比特长度大于链路的比特长度大于PDU长长度时。度时。效率不高效率不高传输时间：站发送一帧所需的时间。传输时间：站发送一帧所需的时间。传播延迟：传播延迟：1位从发送站传播到接收站的时间。位从发送站传播到接收站的时间。假假设设：一一个个报报文文被被分分成成一一系系列列帧帧f1,f2,fn，站站T
3、发发f1;站站R发回一发回一确认确认；站站T发发f2;站站R发回一个发回一个确认确认；站站T发发fn;站站R发回一个发回一个确认确认；则发送数据所需的总时间：则发送数据所需的总时间：性能性能T=nTf tframe =发送一帧所需的时间发送一帧所需的时间tprop =从从T传播到接收站传播到接收站R的时间的时间tack =发送确认帧的时间发送确认帧的时间tproc =每个站处理入境帧的时间每个站处理入境帧的时间U=n tframe n(2 tprop+tframe )=2 tprop+tframetframe Tf =tframe+tprop+tproc+tack+tprop其中：其中：线路利
4、用率线路利用率T=n(2 tprop+tframe )忽略不计忽略不计定义参数：定义参数：a=tprop/tframe 即即 传播延迟传播延迟/传输时间传输时间 U=12a+1线路的最大利用率线路的最大利用率:t0+1+2at0t0+at0+1t0+1+aTTTTTRRRRR传输时间传输时间=1 传播时间传播时间=a 当当a1 链路的比特长度大于帧长链路的比特长度大于帧长TTTTTRRRRR在帧的前在帧的前沿尚未到沿尚未到达目标时，达目标时，源已完成源已完成了一帧的了一帧的发送。发送。线路总是线路总是处于空闲处于空闲状态。状态。距离距离 d=1000km；帧长帧长 L=53B=424b；数据速
5、率数据速率 R=155.52Mbps；传输时间传输时间tframe=424/(155.52*106)=2.7*10-6 s；假设：采用光纤媒体假设：采用光纤媒体例例1 T R ATM则：则：传播延迟传播延迟tprop=106/3*108=0.33*10-2 s；a=0.33*10-2/(2.7*10-6)=1200 U=1/(1+2400)=0.0007例例2卫星卫星250ms250msL=1000b；R=50kps；传播延迟传播延迟=500ms;发送一帧所需的时间发送一帧所需的时间=20ms;t=0 可以发送；可以发送；t=1000/50000=20ms 发完第一帧；发完第一帧；t=20+2
6、50=270ms 接收完第一帧；接收完第一帧；t=270+250=520ms 收到第一帧的应答。收到第一帧的应答。信道利用率信道利用率20/520=3.8%n=1+传播延迟传播延迟发送一帧所需的时间发送一帧所需的时间=26地球地球解决方法：利用传播延迟连续发送解决方法：利用传播延迟连续发送n帧帧支持有连接的支持有连接的LLC服务。服务。两个站两个站(A,B)通过全双工链路连接通过全双工链路连接每个站为每个站为n个帧分配缓冲区个帧分配缓冲区为每个发送的帧分配一个序号为每个发送的帧分配一个序号 工作原理工作原理2.滑动窗口流量控制滑动窗口流量控制 A B如序号用二进制如序号用二进制n位表示，位表示
7、，则取值范围：则取值范围：0,1,2,.2n-1发送窗口发送窗口(WT)：允许发送方连续发送的序号表；允许发送方连续发送的序号表；接收窗口接收窗口(WR)：允许接收方接收的序号表；允许接收方接收的序号表；序号空间：序号的取值范围。序号空间：序号的取值范围。发送窗口发送窗口接收窗口接收窗口01234567012345670序列号序列号已发送的帧已发送的帧可发送帧可发送帧发送的最后帧发送的最后帧发出帧后，窗发出帧后，窗口的下限前移口的下限前移收到确认，窗收到确认，窗口的上限前移口的上限前移01234567012345670已接收的帧已接收的帧可接收帧可接收帧最后确认帧最后确认帧接收帧后，窗接收帧后
8、，窗口的下限前移口的下限前移发出确认，窗发出确认，窗口的上限前移口的上限前移捎带技术：捎带技术：RRn：准备接收从准备接收从n开始的开始的PDU；RNRn：已接收直到已接收直到n-1的所有的所有PDU，但不能再接收了。但不能再接收了。每个站都保持两个窗口每个站都保持两个窗口 流量控制方式流量控制方式 双向传输双向传输控制发送控制发送控制接收控制接收发送窗口发送窗口接收窗口接收窗口双方既发数据又发确认。双方既发数据又发确认。捎带技术与累计确认捎带技术与累计确认PDU（顺序号顺序号+确认号）确认号）收方可对收方可对K帧帧(K2a+1 A A A A B B B B效率达到效率达到1.0t0t0+a
9、t0+a+1t0+2a+1Start of frame1frame1frame1frame2frameaframe3frame2framea+1Start of ACK1framea+2frameNACK1 N2a+1 A A A A B B B BU=N/(2a+1)：指对传输的数据信息进行错误检测。：指对传输的数据信息进行错误检测。112345345timeX?二二.差错控制差错控制 数据帧丢失数据帧丢失 利用超时机制。利用超时机制。应答帧丢失应答帧丢失 利用超时机制出现重复帧。利用超时机制出现重复帧。给每个发送帧编号。给每个发送帧编号。ACK指出期望接收的下一个帧的序号。指出期望接收的下
10、一个帧的序号。数据帧差错数据帧差错 发送发送NAK。自动重发检错方式自动重发检错方式(ARQ，Automatic-Repeat-reQuest)缺点缺点纠错编码：在信息序列中根据某种规则加入一定的校验码。纠错编码：在信息序列中根据某种规则加入一定的校验码。在在自自动动重重发发请请求求中中，数数据据信信息息与与校校验验码码一一起起作作为为一一个个整体进行传输。整体进行传输。适用：对数据通信实时性无严格要求的场合适用：对数据通信实时性无严格要求的场合 优点优点要求有反馈的信道，只要求有反馈的信道，只能用于点点通信。能用于点点通信。检错能力强；检错能力强；校验的码元位数也少。校验的码元位数也少。回退
11、回退NARQ选择重发选择重发ARQ停等式停等式ARQ连续式连续式ARQ ARQ分类分类基于停等流量控制技术基于停等流量控制技术frame0ACK1frame1ACK0frame0Xtimeoutframe0ACK1frame1ACK0Xtimeoutframe1ACK0帧丢失帧丢失A 重发重发ACK0 丢失丢失A 重发重发B 丢弃重丢弃重复帧复帧1.停等式停等式ARQ A B PDU遭破坏遭破坏 ACK被破坏被破坏 实现简单实现简单 如同停等如同停等流控技术一样流控技术一样效率低效率低 基于滑动窗口流量机制基于滑动窗口流量机制F1F0F2F3F4F5F6X？F7F5F6F7F0F1F2RR2e
12、rrorRR4REJ5RR6XRR0timeoutRR(P=1)RR2丢弃丢弃 5,6,7重发重发2.回退回退-N ARQ A B 可能差错可能差错帧被破坏帧被破坏 RR被损坏被损坏发送端连续发出发送端连续发出N个帧，接收端以个帧，接收端以流水线方式顺序流水线方式顺序接收各个帧，并接收各个帧，并进行差错检测。进行差错检测。一旦某个帧有错，一旦某个帧有错，则丢弃该帧和它则丢弃该帧和它之后所收到的所之后所收到的所有帧。有帧。要求每一帧的要求每一帧的ACK在其后第在其后第N个帧尚未结束发送之前到达个帧尚未结束发送之前到达发送端必须有存放发送端必须有存放N帧信息的缓存以便重发帧信息的缓存以便重发接收端
13、只要求有存放一帧的缓冲区接收端只要求有存放一帧的缓冲区要求全双工链路要求全双工链路正正确确帧帧的的重重发发无无疑浪费了信道。疑浪费了信道。回退回退N-ARQ只能接收顺序帧，故又被称为只能接收顺序帧，故又被称为顺序收发方式。顺序收发方式。特点特点 优点优点 缺点缺点消除了停等消除了停等ARQ的等待应答时间。的等待应答时间。若第一帧的若第一帧的ACK在第在第N帧发完以前帧发完以前尚未到达，尚未到达，表明信道往表明信道往返时延较大，返时延较大，可加大帧的可加大帧的长度或增加长度或增加N的值的值01234m-101发方发方收方收方01234m-101ACK1ACKm？WTtimeout 窗口大小窗口大
14、小假设：假设：模模m=2n ，最大序号最大序号Smax =m-1=2n 1 序号空间：序号空间：0,1,2,3,.2n 1 WTm WTm-1 发发送送序序号号：0，1，2，m-2；WTt)为了检出为了检出e个错码，要求码集的汉明距离个错码，要求码集的汉明距离 de+1为纠正为纠正t个错码，要求码集的汉明距离个错码，要求码集的汉明距离 d2t+1例例1：if e=2,t=1,then de+t+1=40001，0010，0100，10001110，1011，1101，01110011，0101，0110，1001，1010，1100能检能检2位错位错能纠能纠1位错位错既能检既能检2个个错码，同
15、时错码，同时能纠正能纠正1个个错码。错码。A：0000 B：1111 d=4编码规则：编码规则：先将所要传送的数据码元分组。在各组的先将所要传送的数据码元分组。在各组的数据后面附加一位校验位，使得该组码连校验位在内数据后面附加一位校验位，使得该组码连校验位在内的码字中的码字中 “1”的个数为偶数的个数为偶数偶校验偶校验 “1”的个数为奇数的个数为奇数奇校验奇校验垂直奇偶校验、水平奇偶校验、垂直水平奇偶校验、斜奇偶校验垂直奇偶校验、水平奇偶校验、垂直水平奇偶校验、斜奇偶校验强强检错能力检错能力能检出码字中任意奇数个错误；能检出码字中任意奇数个错误；随机错误十分有效随机错误十分有效;2.奇偶校验编
16、码奇偶校验编码 垂直奇偶校验垂直奇偶校验发发送送端端在在k位位表表示示字字符符的的信信息息位位上上，附附加加一一个个第第k+1位的校验位；位的校验位；接接收收端端根根据据收收到到的的k位位重重新新产产生生校校验验位位，并并与与第第k+1位作比较。如相同则无错，否则存在错误。位作比较。如相同则无错，否则存在错误。设设b1 b2 bm-1是同一码组内的各个数据码元，是同一码组内的各个数据码元，bm为校验位为校验位偶校验：偶校验：b1 b2 .bm-1 bm=0 bm=b1 b2 .bm-1 奇校验：奇校验：b1 b2 .bm-1 bm=1 bm=b1 b2 .bm-1 1 能发现奇能发现奇数个差错
17、；数个差错；无法发现无法发现偶数个差错；偶数个差错；H Q Z K 4 5 T 7 8 9b1 0 1 0 1 0 1 0 1 0 1b2 0 0 1 1 0 0 0 1 0 0b3 0 0 0 0 1 1 1 1 0 0b4 1 0 1 1 0 0 0 0 1 1b5 0 1 1 0 1 1 1 1 1 1b6 0 0 0 0 1 1 0 1 1 1b7 1 1 1 1 0 0 1 0 0 00 1 0 0 1 0 1 1 1 01 0 1 1 0 1 0 0 0 1字符字符位位偶偶奇奇b8在在传传送送数数据据时时，常常将将若若干干个个字字符符组组成成一一组组信信息息。当当对对一一组内的各字
18、符的同一位进行奇偶校验时，就称为。组内的各字符的同一位进行奇偶校验时，就称为。水平奇偶校验水平奇偶校验可检测出组内各字符同一位上的奇数个错可检测出组内各字符同一位上的奇数个错可检测出突发长度可检测出突发长度字符长度的所有突发错误字符长度的所有突发错误 垂直水平奇偶校验垂直水平奇偶校验 把垂直和水平两个方向的奇偶校验结合起来使用。把垂直和水平两个方向的奇偶校验结合起来使用。可检出可检出3位或位或3位以下的全部错误位以下的全部错误可检出所有的奇数个错可检出所有的奇数个错可检出大部分偶数个错可检出大部分偶数个错可检出长度可检出长度k+1的突发错误的突发错误 H Q Z K 4 5 T 7 8 9b1
19、 0 1 0 1 0 1 0 1 0 1b2 0 0 1 1 0 0 0 1 0 0b3 0 0 0 0 1 1 1 1 0 0b4 1 0 1 1 0 0 0 0 1 1b5 0 1 1 0 1 1 1 1 1 1b6 0 0 0 0 1 1 0 1 1 1b7 1 1 1 1 0 0 1 0 0 0字符字符位位偶偶 奇奇1 01 00 11 00 11 01 0 H Q Z K 4 5 T 7 8 9b1 0 1 0 1 0 1 0 1 0 1b2 0 0 1 1 0 0 0 1 0 0b3 0 0 0 0 1 1 1 1 0 0b4 1 0 1 1 0 0 0 0 1 1b5 0 1 1
20、 0 1 1 1 1 1 1b6 0 0 0 0 1 1 0 1 1 1b7 1 1 1 1 0 0 1 0 0 00 1 0 0 1 0 1 1 1 01 0 1 1 0 1 0 0 0 1字符字符位位偶偶奇奇b8110101110水水 平平3.循环冗余校验码循环冗余校验码(CRC，Cyclic Redundancy check)将要传送的信息分成码组将要传送的信息分成码组M，然后按某一种约定的规然后按某一种约定的规律对每一个信息码组附加一些校验的码元律对每一个信息码组附加一些校验的码元R，形成新的形成新的码组码组C，使得使得C中的码元之间具有一定的相关性中的码元之间具有一定的相关性(即码组
21、即码组中中“1”和和“0”的出现彼此相关的出现彼此相关)，再传输到接收端；，再传输到接收端；接收端根据这种相关性或规律性来校验码组接收端根据这种相关性或规律性来校验码组C是否正是否正确，还可对出错码组的错定位加以相应的纠正，最后将确，还可对出错码组的错定位加以相应的纠正，最后将码组码组C还原成信息码组还原成信息码组M。基本思想基本思想 线性分组码与循环码线性分组码与循环码如如果果分分组组码码的的码码组组结结构构规规则则或或规规律律性性可可用用线线性性方方程程来来描描述，则这种分组码称为，否则就是非。述，则这种分组码称为，否则就是非。例：奇偶校验码例：奇偶校验码 偶校验：偶校验：b1 b2 .b
22、m-1 =bm 奇校验：奇校验：b1 b2 .bm-1 1=bm线性分组码线性分组码循循环环移移位位特特性性：码码集集中中任任一一码码字字每每次次向向左左(或或右右)循循环环移移位得到的是码集中的另一个码字。位得到的是码集中的另一个码字。循环码循环码具有循环移位特性的线性分组码。具有循环移位特性的线性分组码。封闭性：封闭性：码集中任何两个码字相加后形成的新序列仍码集中任何两个码字相加后形成的新序列仍是该码集中的一个码字。是该码集中的一个码字。码多项式及其算术运算码多项式及其算术运算假设循环码假设循环码 C=Cn-1 Cn-2.C2 C1 C0，长度为长度为nC的的码多项式码多项式（称为（称为n
23、-1次多项式次多项式）C(x)=Cn-1 xn-1+Cn-2xn-2+.C2 x2+C1 x+C0例例1：C=1100101 C(x)=1x6+1x5+0 x4+0 x3+1x2+0 x+1 =x6+x5+x2+1码多项式的算术运算：模码多项式的算术运算：模2加、模加、模2减、模减、模2乘、模乘、模2除。除。循环码循环码(n，k)用多项式表示：用多项式表示：C(x)=Cn-1 xn-1+Cn-2xn-2+.Cn-k xn-k+Cn-k-1xn-k-1.C2x2+C1x+C0定理：在一个定理：在一个(n，k)循环码中，存在一个且只有一个循环码中，存在一个且只有一个(n-k)次的码多项式次的码多项
24、式 g(x)=xn-k+gn-k-1xn-k-1+.g2 x2+g1 x+1满足下列两个条件：满足下列两个条件：循环码的生成多项式循环码的生成多项式此循环码中任一码多项式都是此循环码中任一码多项式都是g(x)的倍式的倍式任意一个任意一个(n-1)次或次或(n-1)次以下又是次以下又是g(x)倍式倍式的多项式必定是此循环码的一个码多项式的多项式必定是此循环码的一个码多项式对对于于一一个个码码长长为为n，信信息息码码元元为为k位位的的循循环环码码(n，k),其其构成形式为：构成形式为：12knk+1 k+2k位位r位位n位位信息码元信息码元校验码元校验码元每个码多项式的前面每个码多项式的前面k项与
25、待编码的信息多项式相同项与待编码的信息多项式相同后面的后面的r=n-k项与校验码元序列对应的校验多项式相同项与校验码元序列对应的校验多项式相同 循环码的编码循环码的编码设要编码的设要编码的k位信息元为：位信息元为：m=(mk-1,mk-2,.m1,m0)m(x)=mk-1 xk-1+mk-2xk-2+.+m1 x+m0 xn-km(x)=mk-1 xn-1+mk-2xn-2+.+m1 xn-k+1+m0 xn-k =q(x)g(x)+r(x)(1)其中：其中：g(x)是是(n-k)次多项式次多项式 q(x)是商式是商式 r(x)是余式，且次数不高于是余式，且次数不高于n-k-1，即即 r(x)
26、=rn-k-1 xn-k-1+rn-k-2xn-k-2+.+r1 x+r0 (2)将等式（将等式（1）变换成）变换成 xn-km(x)+r(x)=q(x)g(x)(3)mk-1xn-1+mk-2xn-2+.+m1xn-k+1+m0 xn-k+rn-k-1xn-k-1+rn-k-2xn-k-2+.+r1 x+r0 （mk-1,mk-2,.m1,m0,rn-k-1,rn-k-2,.,r1,r0）不加改变的不加改变的k个信息位个信息位(n-k)个监督位个监督位(1)设生成多项式设生成多项式g(x)的最高幂次为的最高幂次为r=n-k(2)将待编码码元序列表示为将待编码码元序列表示为m(x)，乘以乘以x
27、r，结果左移结果左移r位位xrm(x)(3)用用g(x)去除去除 xrm(x)，求得商式求得商式q(x)和和余式余式r(x)xrm(x)/g(x)=q(x)+r(x)/g(x)xrm(x)=q(x)g(x)+r(x)xrm(x)+r(x)=q(x)g(x)xrm(x)+r(x)：为除法运算后变成的循环多项式为除法运算后变成的循环多项式C(x)的表示式的表示式 r(x)：余数多项式即为余数多项式即为校验多项式，校验多项式，其系数其系数Cr-1，Cr-2，.C1，C0为为校验码校验码C(x)=Cn-1xn-1+Cn-2xn-2+.+Cn-kxn-k+Cn-k-1xn-k-1+C2x2+C1x+C0
28、 =Cn-1 xn-1+Cn-2xn-2+Cn-kxn-k+Cr-1xr-1+Cr-2xr-2 C2x2+C1x+C0 校验码的产生校验码的产生校验码校验码信息码信息码例：设编码的信息码元为例：设编码的信息码元为1101011011 m(x)=x9+x8+x6+x4+x3+x+1,k=10(1)假设假设 g(x)=x4+x+1 系数形成的位串为系数形成的位串为10011 r=4-n=14 r(x)的最高幂次为的最高幂次为 r-1=3(2)x4m(x)=1101011011，0000(3)1101011011.0000 10011 商数：商数：1100001010 余数：余数：1110 r(x)
29、=x3+x2+x+0所需的循环编码所需的循环编码C(x)为为C(x)=xrm(x)+r(x)=1101011011，11101 1 0 1 0 1 1 0 1 1,0 0 0 01 0 0 1 11 0 0 1 11 0 0 1 11 0 0 1 11 0 1 1 01 0 0 1 11 0 1 0 01 0 0 1 11 1 1 01 1 0 0 0 0 1 0 1 0商数商数余数余数 r(x)除数除数 g(x)被除数被除数 m(x)规规则则3：被被除除数数或或部部分分余余数数的的最最高高位位为为1，且且位位数数大大于于等等于于除除数数位位数数时时商商便为便为1。规则规则1：不涉及：不涉及小数。当余数位小数。当余数位小于除数位时便小于除数位时便结束除法过程。结束除法过程。规则规则2：减法为：减法为模模2减。减。