《计算机通信网 》第3章 数据链路层Part2

1、作业作业41、请写出通常采用的成帧方法及各种成帧法的特、请写出通常采用的成帧方法及各种成帧法的特点。假设帧标记符出错，请问哪种成帧方法将点。假设帧标记符出错，请问哪种成帧方法将不能检测到后续所有的帧？为什么？不能检测到后续所有的帧？为什么？2、如果待传数据为、如果待传数据为 1111111000111111，假，假设采用设采用“位填充法位填充法”成帧，请写出帧内容。成帧，请写出帧内容。3、假设待传数据为、假设待传数据为 100101，（，（1）计算校验位）计算校验位r的位数；（的位数；（2）计算出传输该数据的海明码）计算出传输该数据的海明码（要求步骤）（要求步骤）4、假设待传数据为、假设待传数

2、据为100101，采用，采用CRC编码，假编码，假设生成多项式为设生成多项式为G（X）=X4+1，计算出校验，计算出校验多项式多项式R（X）。）。3.4 差错与流量控制协议差错与流量控制协议n在计算机网络中，差错控制方式通常采用在计算机网络中，差错控制方式通常采用 自动请求重发（自动请求重发（ARQ ）nARQ基本思想：基本思想：n采用检错码进行检错采用检错码进行检错n丢弃出错的帧丢弃出错的帧n请求重传出错的帧请求重传出错的帧n对帧进行确认对帧进行确认n典型的典型的ARQ协议协议n停等协议停等协议n回退回退N协议协议n选择性重传协议选择性重传协议nARQ是一种保证是一种保证PDU可靠传输的技术

3、可靠传输的技术n可用于各层协议中，不仅仅限于数据链路层可用于各层协议中，不仅仅限于数据链路层n 例如：例如：nX.25网络的网络层、数据链路层网络的网络层、数据链路层nTCP/IP网络中的传送层网络中的传送层3.4 差错与流量控制协议差错与流量控制协议n3.4.1 停停等协议等协议n3.4.2 连续发送的滑动窗口协议的概念连续发送的滑动窗口协议的概念n3.4.3 回退回退N协议协议n3.4.4 选择性重传协议选择性重传协议n3.4.4 双向传输时的确认双向传输时的确认n3.4.4 流量控制流量控制3.4.1停停等协议等协议n停停等协议：等协议：stop and wait protocoln基本

4、思想：基本思想：n每发送一个每发送一个帧（帧（PDU），），停下来等确认（应答）停下来等确认（应答）n收到肯定应答，发送下一个新帧（收到肯定应答，发送下一个新帧（PDU）n收到否定应答，重发上次的帧收到否定应答，重发上次的帧 ACK新新PDUNAKDATADATA新新PDUDATA网网络络层层链路层链路层链路层链路层网网络络层层重发重发PDUDATAACKl 数据链路层的数据链路层的 PDU也称为帧也称为帧l 后续讨论中帧后续讨论中帧 和和PDU等同等同3.4.1停停等协议等协议 协议需要考虑以下情况协议需要考虑以下情况n帧丢失，将导致：帧丢失，将导致：n接收方收不到接收方收不到PDUn发送方

5、收不到应答（发送方收不到应答（ACK或或NAK）n应答丢失，将导致：应答丢失，将导致：n发送方收不到应答（发送方收不到应答（ACK或或NAK）n解决办法：设置定时器解决办法：设置定时器T，超时重发，超时重发PDUPDUACKTPDUPDUACKT重传重传重传重传3.4.1停停等协议等协议n还有问题要解决：还有问题要解决：n连续丢失问题连续丢失问题n重发后仍收不到应答或接收方仍收不到重发后仍收不到应答或接收方仍收不到PDU，一直重发下去？，一直重发下去？n解决办法：设置重发次数解决办法：设置重发次数Nmaxn重复收帧问题重复收帧问题nACK丢失，重发丢失，重发PDU，接收方收到重复帧而不知道，接

6、收方收到重复帧而不知道n措施：为措施：为PDU编号（编号（0 1即可区别）即可区别）重复重复PDU丢弃丢弃PDU（0）PDU（0）ACKT重传重传PDU有编号有编号不出错不出错PDUPDUACKT重传重传新新PDU？PDU无编号无编号会出错会出错3.4.1停停等协议等协议n还有问题要解决：还有问题要解决：n过早超时问题过早超时问题n重发定时器重发定时器T在应答到达发送方之前就超时在应答到达发送方之前就超时n导致接收方正确收到导致接收方正确收到PDU，而发送方仍然重发，而发送方仍然重发n如果过早超时，且如果过早超时，且ACK无编号，则无编号，则n出现发送出现发送PDU出错出错n措施：对应答编号措

7、施：对应答编号n请同学自己分析以下情况：请同学自己分析以下情况：n过早超时，但过早超时，但PDU和和ACK都编号时，都编号时， 停等协议将如何工作？停等协议将如何工作？重复重复PDU丢弃丢弃PDU（0）PDU（0）ACKT重传重传PDU（1）ACKPDU（0）发送方误以为是对发送方误以为是对PDU（1）的应答，故下一）的应答，故下一个发个发PDU（0） 出错！出错！数据帧编号数据帧编号DUDUN校验校验TDUDUN校验校验TIf(N=Vr)Vr+;N=VsVs+;对对DU顺序编号顺序编号DU顺序提交上层顺序提交上层发送变量发送变量Vs实现实现对对DU的顺序编号的顺序编号接收变量接收变量Vr控制

8、控制DU的顺序提交的顺序提交DUN校验校验TN=帧序号帧序号,0,1,2,T=帧类型，帧类型，DATA，ACK，TQ(待发送队列待发送队列)记为记为Fm(N)Fm(N)数据封装实现数据封装实现(扩)n用用skbBuff实现实现MAC实体实体IP实体实体DataLenDataPospPDUOnSend(pPDU)skbPush(pPDU,sizeof(FmHdr);pHdr = skbGetDataPtr(pPDU);pHdrType= Send(pPDU) to lowerStruct skbBuff *pPDU;Struct FmHdr pHdr;Deliver(pHdrType, pPDU

9、);skbPop(pPDU,sizeof(FmHdr);Do some recv things(pHdr)pHdr = skbGetDataPtr(pPDU);OnRecv(pPDU) From lowerMAC实体实体DataLenDataPosskbPush(pPDU,len)lenskbGetDataPtr(pPDU)SAPSAP数据帧编号数据帧编号(扩)typedef struct FmHdr U8 Type; / Frame Type U8 seqN; / Frame number FmHdr；#define FM_DATA 1#define FM_ACK 2int Vs = 0;i

10、nt Vr = 0；OnSendReq(SKB *pSkb) FmHdr *pF; skbPush(pSkb, sizeof(FmHdr); pF = (FmHdr*)skbGetDataPtr(pSkb); pF-Type = FM_DATA; pF-seqN = Vs+; EnQue(TQ, pSkb);OnFmInd(SKB *pSkb) FmHdr *pF; pF = (FmHdr*)skbGetDataPtr(pSkb); skbPop(pSkb, sizeof(FmHdr); if(pF-seqN = Vr) NetRx(pSkb); Vr+; else skbFree(pSkb)

11、;超时重传超时重传TQ取出一帧发送取出一帧发送送入重传队列送入重传队列TimerStartTimer等待应答等待应答RTQStopTimer应答到应答到取出一帧发送取出一帧发送TimeOutStartTimer重传队列重传队列WaitACK() int Retry=0； while(1) event = WaitEvent(); / 无事件时，阻塞软件执行无事件时，阻塞软件执行 switch(event) case T0: pSkb=GetEntry(RTQ);/ 从队列中获得但不取出从队列中获得但不取出 SendFrame(pSkb); StartTimer(T0); Retry+; if

12、(ReTry = MaxTry) return -1; break; case ACK: pSkb = DeQue(RTQ); skbFree(pSkb); StopTimer(T0); return 0; break; 超时重传（扩）超时重传（扩）int SendTask() int continue = 1; while (continue) pSkb=DeQue(TQ); SendFrame(pSkb); EnQue(RTQ,pSkb); StartTimer(T0); if( WaitACK() seqN = Vr) NetRx(pSkb); Vr+; / for next frame

13、 else skbFree(pSkb); SendACK(Vr);3.4.3 回退回退n帧协议（帧协议（Go back n）n是一个发送窗口为是一个发送窗口为Ws，接收窗口为，接收窗口为1的滑动窗口协议的滑动窗口协议 教材教材.n 基本思想基本思想n发送方发送方n一次可连续发送多个一次可连续发送多个PDUn始终维持未应答的始终维持未应答的PDU个数某一个值（发送窗口大小）个数某一个值（发送窗口大小）n超时重发窗口未被确认的所有超时重发窗口未被确认的所有PDU（回退（回退n）n接收方接收方n一个一个地按序收一个一个地按序收PDUn序号及内容正确的序号及内容正确的PDU，数据上交上层，数据上交上层

14、n出错的出错的PDU及后续（非期望）的及后续（非期望）的PDU全部丢弃。全部丢弃。 n要求：要求：n发送缓冲区为发送缓冲区为Ws个个n接收缓冲区为接收缓冲区为13.4.3 回退回退n帧协议（帧协议（Go back n） 发送窗口滑动举例发送窗口滑动举例n假设；用假设；用3位二进制对位二进制对PDU编号，发送窗口编号，发送窗口 Ws=4 PDU编号为编号为0、17循环使用循环使用n假设：已连续发送了假设：已连续发送了03号号PDU，等应答，等应答 则：则： 窗口内的窗口内的PDU为为0-3号号n如收到如收到ACK（2），则），则n将窗口底部移到将窗口底部移到2，窗口顶部向前移，保持窗口大小为，窗

15、口顶部向前移，保持窗口大小为Ws=4，此时新窗口内的，此时新窗口内的PDU为为2、3、4、524670135012345673.4.3 回退回退n帧协议（帧协议（Go back n）假设假设PDU编号为编号为3位二进制数，位二进制数，Ws=4每帧确认，每帧确认，ACK（K）表示希望收下一个）表示希望收下一个PDU（K）5601245601234超时超时5346丢弃丢弃7120573460ACK（3）收到收到PDU（2）下一个收下一个收PDU（3）回退整个窗回退整个窗口，重发口，重发3.4.3 回退回退n帧协议（帧协议（Go back n） 协议运行原理协议运行原理n发送方发送方n窗口尺寸：窗口

16、尺寸：1Ws2N-1，最多连续发送窗口中的，最多连续发送窗口中的Ws个个PDUn窗口滑动：收到期望的窗口滑动：收到期望的Ack(k)：窗口底部移到：窗口底部移到 PDU（k），窗口顶部向前移动，始终保持窗口里有），窗口顶部向前移动，始终保持窗口里有Ws个个PDU未确认未确认n窗口滑动后，发送新进入窗口的窗口滑动后，发送新进入窗口的PDUn超时重发：超时重发： 超过超过T未收到期望的未收到期望的Ack，重发窗口中的，重发窗口中的PDU(回退整个窗口回退整个窗口)n超次数失败：超过最大重发次数超次数失败：超过最大重发次数Nmax仍无正确应答仍无正确应答3.4.3 回退回退n帧协议（帧协议（Go b

17、ack n） 协议运行原理协议运行原理n接收方接收方n窗口尺寸：窗口尺寸：Wr=1n按序接收：按照按序接收：按照PDU编号依序接收，出错、乱序编号依序接收，出错、乱序PDU一一律丢弃律丢弃n确认含义：确认含义：Ack(k)表示对表示对k-1及以前各编号的及以前各编号的PDU的确的确认，同时期望接收第认，同时期望接收第k号号PDUn确认策略：确认策略： 按序到达的按序到达的PDU可立即确认，也可延迟确认可立即确认，也可延迟确认(收到多帧后一起确认收到多帧后一起确认)，但出错或乱序的，但出错或乱序的PDU，确认，确认Ack(k)（期望接收（期望接收k号号PDU）或不应答）或不应答3.4.3 回退回

18、退n帧协议（帧协议（Go back n）如果如果Ws 2N，会出现什么情况？，会出现什么情况？（协议会失败！）（协议会失败！）假设：假设：N=2，则，则PDU为为0-3号（号（4个）循环使用个）循环使用超时超时2013201320132013重复，无法分辨重复，无法分辨ACK（0）希望下一个收希望下一个收PDU（0）Ws=4，协议失败，协议失败超时超时201201201201重复，丢弃重复，丢弃ACK（3）希望下一个收希望下一个收PDU（3）Ws=34 ,则协议运行正常则协议运行正常3.4.3 回退回退n帧协议帧协议nSelect the go back Number Nn发送发送PDUi时，

19、继续发送后续的时，继续发送后续的PDU，直到，直到“预期预期”收收到到ACKi+1的时刻为止的时刻为止n可持续发送可持续发送N个个PDU：PDUi . PDUi+N-1n发送序号超前应答序号发送序号超前应答序号N2 tN1+ t2 3.4.4 选择性重传协议选择性重传协议（selective repeat）n发送窗口为发送窗口为Ws，接收窗口为，接收窗口为Wr的滑动窗口协议的滑动窗口协议 教材教材.3n 基本思想基本思想n改进回退改进回退n帧协议由于一个帧协议由于一个PDU错，需重传后续多个错，需重传后续多个PDU的问题的问题n发送方发送方n对应一个发送窗口，可连续发送窗口内的多个对应一个发送

20、窗口，可连续发送窗口内的多个PDU，并保持未被确认的，并保持未被确认的PDU个数为窗口值个数为窗口值n只重发接收方指定序号的只重发接收方指定序号的PDU或超时的或超时的PDUn接收方接收方n也对应一个接收窗口，接收序号落在窗口内的也对应一个接收窗口，接收序号落在窗口内的PDU，存储出错的后续，存储出错的后续PDU及乱序的及乱序的PDUn窗口外窗口外PDU一律丢弃，指定需重发的一律丢弃，指定需重发的PDU，排序并按序上交数据，排序并按序上交数据n要求：要求：n发送缓冲区为发送缓冲区为Ws个个n接收缓冲区为接收缓冲区为Wr个个3.4.4选择性重传协议选择性重传协议n除正常的应答除正常的应答ACK（

21、K）外，增加一个否定应答）外，增加一个否定应答NAK（K），两者含义不同：），两者含义不同：nACK（K）：表示收方已正确收到）：表示收方已正确收到K-1及以前所有及以前所有的的PDU，希望下一个接收，希望下一个接收K号号PDU，K号及后续的号及后续的PDU一定还未收到一定还未收到nNAK（K）：表示第）：表示第K号号PDU出错或丢失，但出错或丢失，但K号号前的所有前的所有PDU收到，希望重发第收到，希望重发第K号号PDU，还隐含，还隐含K号以后的后续号以后的后续PDU可能已收到，只等可能已收到，只等PDU（K）的到来，重新排序后便可按序上交的到来，重新排序后便可按序上交3.4.4选择性重传协

22、议选择性重传协议 协议运行原理协议运行原理n发送方发送方n窗口尺寸：窗口尺寸：1Ws2N/2，最多连续发送窗口中的，最多连续发送窗口中的Ws个个PDUn窗口滑动：与回退窗口滑动：与回退n帧协议相同帧协议相同n选择重发：收到选择重发：收到NAK（K），重发），重发PDU（K）n超时重发：超过超时重发：超过T未收到期望的未收到期望的ACK，重发当前超时未应，重发当前超时未应答的答的PDUn超次数失败：超过最大重发次数超次数失败：超过最大重发次数Nmax仍无正确应答，仍无正确应答，报告上层失败报告上层失败3.4.4选择性重传协议选择性重传协议 协议运行原理协议运行原理n接收方接收方n窗口尺寸：窗口尺

23、寸：12N，会出现什么情况？会出现什么情况？（协议会失败！）（协议会失败！）假设：假设：N=2，则，则PDU为为0-3号（号（4个）循环使用个）循环使用Ws=3，Wr=2 协议失败协议失败201200121012重复重复0不能辨认不能辨认ACK（3）ACK（1）超时超时NAK（3）n Ws初始为：初始为：0，1，2n Wr初始为：初始为：0，1，正确收到，正确收到0和和1帧，帧， 发发ACK，窗口变为：，窗口变为：2，3n 收到收到PDU（2），发），发ACK（3），）， 窗口为：窗口为：3，0，所有，所有3个应答均丢失。个应答均丢失。 n 发端超时重发均超时的发端超时重发均超时的PDU（0）

24、 PDU（2），而），而PDU（0）在接收新窗）在接收新窗口内，收端不知是重发，当作新数据存起口内，收端不知是重发，当作新数据存起来，发来，发NAK（3）3.4.5 双向传输时的确认双向传输时的确认n双向数据传输双向数据传输n独立保证每个方向的传输可靠性独立保证每个方向的传输可靠性n站点间一般只有一对双向信道站点间一般只有一对双向信道发送方发送方接收方接收方接收方接收方发送方发送方Link-ALink-B发送方发送方接收方接收方接收方接收方发送方发送方Link-ALink-B两对双向信道上实现两对双向信道上实现 可得到及时应答可得到及时应答 应答信道利用不充分应答信道利用不充分一对双向信道上实

25、现一对双向信道上实现 数据和应答在时间上相互影响数据和应答在时间上相互影响 双向信道都能充分利用双向信道都能充分利用3.4.5 双向传输时的确认双向传输时的确认n捎带确认捎带确认发送方发送方接收方接收方接收方接收方发送方发送方Link-ALink-Btypedef struct FmHdr U8 Type; / Frame Type U8 seqN; / Frame number U8 ackN; / ACK number FmHdr；Fm(i,k)=Fm(i)和和ACK(k)的组合的组合VsVrVrVs站点维持两个变量站点维持两个变量Vs和和Vr Vs控制发送，控制发送，Vr控制接收控制接收

26、注意：注意： Vs和和Vr的值是相互独立的的值是相互独立的Fm(2,4)Fm(3,4)Fm(Ns=Vs, Nr=Vr)Fm(4,2)Fm(4,3)3.4.6 流量控制流量控制n流控问题流控问题n当接收方因某种原因暂时无法接收数据帧时当接收方因某种原因暂时无法接收数据帧时n是不应答发送方，让发送方超时重发来缓解是不应答发送方，让发送方超时重发来缓解n若不应答时间过长，可能造成发送方多次重发后放弃通信若不应答时间过长，可能造成发送方多次重发后放弃通信n发送方似乎应该暂停这种无谓的重发发送方似乎应该暂停这种无谓的重发n应该采用某种机制，通知发送方暂停应该采用某种机制，通知发送方暂停Fm(i)Fm(i

27、)不应答不应答不应答不应答流量控制流量控制n流控技术流控技术n定义新的应答帧定义新的应答帧RNR(Nr), Receive Not ReadynNr表示：表示：Nr-1号帧已收到，期望但暂停号帧已收到，期望但暂停Nr号帧发送号帧发送n当接收方需要暂停接收时当接收方需要暂停接收时n向发送方发向发送方发RNR(Nr)n发送方暂停等待，而不是超时重发发送方暂停等待，而不是超时重发n当接收方可继续接收时当接收方可继续接收时n向发送方发送除向发送方发送除RNR外其他的应答帧外其他的应答帧(Nr)nNr表示期望的帧序号表示期望的帧序号n发送方解除暂停状态，继续帧序列的发送发送方解除暂停状态，继续帧序列的发

28、送Fm(i)RNR(i+1)暂停发送暂停发送ACK(i+1)Fm(i+1)流量控制流量控制n流量控制流量控制流量控制是避免快的发送方淹没慢的接收方，使收发速率流量控制是避免快的发送方淹没慢的接收方，使收发速率适配适配常用的流量控制方法：常用的流量控制方法：方法方法1：接收方缓存快满时，向发送方发送一个流控消息：接收方缓存快满时，向发送方发送一个流控消息 告知自己暂时不能接收告知自己暂时不能接收PDU ，有空间后再通知对，有空间后再通知对 方继续（方继续（HDLC采用）采用）方法方法2：直接关闭接收窗口（：直接关闭接收窗口（TCP采用）采用）ARQ协议小结协议小结n差错控制基本方法差错控制基本方

29、法对对PDU编号编号存储未确认的存储未确认的PDU以便对以便对PDU重发重发接收接收方对方对PDU确认确认对正确的对正确的PDU发发ACK 策略策略1： ACK（K），对），对K及之前序号的确认，希望及之前序号的确认，希望 收收 K+1号号策略策略2(超前应答超前应答) ： ACK（K），对），对K-1及之前序号的及之前序号的确认，希望收确认，希望收K号号对错误的对错误的PDU发发NAK或什么也不发或什么也不发可能稍带确认可能稍带确认发送方触发送方触发重发发重发对每个已发对每个已发PDU设置计时器，超时未收到确认，则重发设置计时器，超时未收到确认，则重发对收到对收到NAK的的PDU重发重发重发

30、内容：重发内容： 回退回退N：重发窗口内所有：重发窗口内所有PDU 选择性重发：只重发超时的和选择性重发：只重发超时的和NAK的的PDUARQ协议小结协议小结nPDU的编号（循环使用）的编号（循环使用）n停等协议停等协议n1位二进制数表示，编号为位二进制数表示，编号为0、1两个两个n回退回退N和选择性重传：和选择性重传：nN位二进制数表示，编号为位二进制数表示，编号为0，1 . 2N-1n窗口大小窗口大小n停等协议：停等协议：n发送窗口发送窗口Ws=接收窗口接收窗口Wr=1 n回退回退N协议：协议：n 1Ws2N-1，Wr=1 注意：注意： Ws不能等于不能等于2N（PDU最大序号数最大序号数

31、+1）n选择性重传协议：选择性重传协议：n1Ws2N/2， 1Wr2N/2 注意实际的条件：注意实际的条件：Ws+Wr不能大于不能大于2Nn提醒：提醒：Ws与与Wr并无直接关系并无直接关系n缓存大小缓存大小n与窗口大小一致。与窗口大小一致。注意：不是与注意：不是与PDU的个数一致的个数一致3.5 协议描述和验证协议描述和验证n为什么要描述协议？为什么要描述协议？引入：协议的描述方法引入：协议的描述方法xn协议规范通常采用自然语言协议规范通常采用自然语言易阅读，但不严格和精确，理解上易出现二义性易阅读，但不严格和精确，理解上易出现二义性 文档文档RFCxxxx 文档的一般格式文档的一般格式n时序

32、图时序图直观，但零散只针对特殊情况直观，但零散只针对特殊情况Introduction Glossary Content OverviewBodyReference时序图的一般格式时序图的一般格式connection_request( )connection_indication( )connection_response( )connection_confirmation( )N+1NN+1SABMEUAt上下层实上下层实体间接口体间接口上下层实上下层实体间事件体间事件对等层实对等层实体间事件体间事件N对等层对等层对等层对等层时间时间描述方式直观描述方式直观但过于零散但过于零散协议描述和验证协

33、议描述和验证n时序图描述时序图描述如此的时间图仅能描述双方配合的某些特例，如此的时间图仅能描述双方配合的某些特例，难以描述所有可能出现的情况。否则，设计难以描述所有可能出现的情况。否则，设计协议软件的人会问：协议软件的人会问：如果双方都同时向对方发送如果双方都同时向对方发送SARM该如何处理？该如何处理？如果双方的应答有一个丢失了，怎么办？如果双方的应答有一个丢失了，怎么办？如果一方发送数据，另一方却回到如果一方发送数据，另一方却回到closed,怎么办？怎么办？如果一方发送数据时又收到对方的如果一方发送数据时又收到对方的SARM如何处理？如何处理？如果数据序号和应答的序号差异太大，该如何处理

34、？如果数据序号和应答的序号差异太大，该如何处理？ 协议应该把这些配合过程都描述清楚，否则协议应该把这些配合过程都描述清楚，否则协议是无法实现的，也不可能正常工作协议是无法实现的，也不可能正常工作!SARMUAF(0)RR(1)xTOF(0)3.5.1有限状态机有限状态机Finite State Machinen一种直观、全局、准确的协议描述方法一种直观、全局、准确的协议描述方法状态状态转移转移事件事件动作动作缺点缺点时序时序性不性不强强TCP协议的状态机协议的状态机有限状态机有限状态机FSMn事件事件n来自实体外部，触发实体产生动作、改变状态来自实体外部，触发实体产生动作、改变状态n收到报文收

35、到报文(数据帧、应答帧、定时器到等数据帧、应答帧、定时器到等)n动作动作n实体对外部或内部的操作实体对外部或内部的操作n发送帧，滑动窗口、改变状态变量等操作发送帧，滑动窗口、改变状态变量等操作n状态状态n实体在一系列事件之间的记忆效应实体在一系列事件之间的记忆效应状态状态事件事件动作动作系统系统(有记忆效应有记忆效应)激励激励响应响应对比：信号与系统对比：信号与系统e(t)h(s,t) (s=状态状态)r(t)协议实体协议实体线性时不变系统线性时不变系统线性时变系统线性时变系统有限状态机有限状态机FSMn事件、动作、状态事件、动作、状态Open发送发送(ConnReq)ConnACKClose

36、dReq SentReadyPacketWait发送发送F(0)RR(1)Ready1 0ClosedOpenReq sentConnReqConnACKReadyPacketF(0)WaitRR(1)Ready发送发送F(1)PacketF(1)WaitTime OutF(1)RR(0)RR(0)ReadyTime Out协议实体协议实体时间图时间图建立连接请求，等待应答建立连接请求，等待应答收到应答，准备通信收到应答，准备通信上层上层Packet, 发送，等待响应发送，等待响应收到正确应答，准备下一帧收到正确应答，准备下一帧等待超时，重发当前帧等待超时，重发当前帧有限状态机有限状态机FSM

37、n一个有限状态机由哪些元素组成？一个有限状态机由哪些元素组成？n状态、事件、动作状态、事件、动作n转移（变迁）转移（变迁）n状态状态n状态机有有限个状态状态机有有限个状态（指稳定状态）（指稳定状态）n每一时刻只能处于一个特定状态中，并等待某个事件的发生每一时刻只能处于一个特定状态中，并等待某个事件的发生n事件事件n如收到如收到PDU，时间超时等都为事件，时间超时等都为事件n事件可能会引起实体动作事件可能会引起实体动作n事件是状态转移的必要条件事件是状态转移的必要条件n动作动作n处理队列中的某个事件，转移到一个状态处理队列中的某个事件，转移到一个状态n不同状态下，对同一事件处理可能不同不同状态下

38、，对同一事件处理可能不同n可能忽略事件，保持原状态可能忽略事件，保持原状态FSM事件事件状态状态State 1State 2状态转移状态转移事件事件2/动作动作2事件事件3/动作动作3事件事件1/动作动作1有限状态机有限状态机FSMn以停等协议为例，说明：以停等协议为例，说明：n状态机的位置在哪里？状态机的位置在哪里？n状态如何确定？（难点）状态如何确定？（难点）n发送方状态机发送方状态机n接收方状态机接收方状态机n协议系统状态机协议系统状态机n考虑发送、接收和信道情况考虑发送、接收和信道情况停等协议状态机的位置停等协议状态机的位置获取获取SDU状态机状态机递交递交SDU发送发送PDU、ACK

39、接收接收PDU、ACK去对等去对等实体实体对等实对等实体来体来协议实体协议实体停等协议状态机的状态停等协议状态机的状态n发送方：两个状态：发送方：两个状态：准备发送帧准备发送帧0 、准备发送帧、准备发送帧1n接收方：两个状态：接收方：两个状态：等待帧等待帧0 、等待帧、等待帧1ACK(1)PDU（1）ACK(0)DATAPDU（0）PDU（0）DATAACK(1)DATADATADATADATA准备发送帧准备发送帧1准备发送帧准备发送帧0等待帧等待帧1等待帧等待帧0n状态是复合的，可能由状态是复合的，可能由多个要素组成：多个要素组成：如：接收方等待帧如：接收方等待帧1 l刚收到帧刚收到帧0 ，

40、正确，正确l已上交数据已上交数据l已发送已发送ACK发送方发送方接收方接收方停等协议发送方状态机停等协议发送方状态机准备发送帧准备发送帧1准备发送帧准备发送帧0收到收到ACK（1）发送帧发送帧1超时超时重发帧重发帧0超时超时重发帧重发帧1收到收到ACK（0）发送帧发送帧0收到收到NAK（0）重发帧重发帧0收到收到NAK（1）重发帧重发帧1注意：注意：ACK（1）：表示接收方已收到帧）：表示接收方已收到帧0，希望下一帧收帧，希望下一帧收帧1此处此处NAK（0）和和ACK（0），），对发方含义一样对发方含义一样停等协议接收方状态机停等协议接收方状态机等待帧等待帧0等待帧等待帧1收到帧收到帧0发发A

41、CK（1）超时超时发发ACK （0）或不发送但或不发送但重置重置T收到帧收到帧1发发ACK（0）收到错帧收到错帧NAK（0）/或不发送或不发送收到错帧收到错帧NAK（1）/或不发送或不发送超时超时发发ACK （1）或不发送但或不发送但重置重置T停等协议状态机的状态（另一种理解）停等协议状态机的状态（另一种理解）准备发送准备发送等待应答等待应答SDU已从上层来已从上层来发送帧发送帧seq=（s=Ns）Ns+超时超时重发帧重发帧收到收到ACK（s+1）收到收到NAK（s）重发帧重发帧Ns为为发送的发送的PDU序号序号发送方发送方等待接收等待接收PDU（S=Nr），期望的），期望的PDU上交上交SD

42、U，Nr+,发发ACK错或非期望的错或非期望的PDUNAK（Nr）超时超时ACK（Nr）Nr为期望接收的为期望接收的PDU序号序号接收方接收方事件产生，并没事件产生，并没有动作，但发生有动作，但发生了状态转移了状态转移进一步理解有限状态机进一步理解有限状态机n同一种协议的状态机可能不是唯一的同一种协议的状态机可能不是唯一的n不同的理解和出发点考虑不同的理解和出发点考虑n只要是稳定的状态并能描述协议即可只要是稳定的状态并能描述协议即可n事件是状态转移的必要条件事件是状态转移的必要条件n事件产生动作事件产生动作n可能产生状态转移可能产生状态转移n也可能不产生状态转移也可能不产生状态转移n事件有时不

43、产生动作，也可产生状态转移事件有时不产生动作，也可产生状态转移n动作一定需要事件来触发，没有事件的动作所产生的动作一定需要事件来触发，没有事件的动作所产生的状态是不稳定的状态是不稳定的State 1状态转移状态转移事件事件1/动作动作1事件事件1/或或事件事件2/动作动作2或或 事件事件2/State 1状态转移状态转移/动作动作1根据有限状态机形成状态转移表根据有限状态机形成状态转移表 状态状态 事件事件动作动作事件事件1事件事件2事件事件2事件事件n状态状态1处理处理下一状态下一状态状态状态2处理处理下一状态下一状态状态状态n处理处理下一状态下一状态停等协议发送状态转移表停等协议发送状态转

44、移表准备发送帧准备发送帧1准备发送帧准备发送帧0收到收到ACK（1）发送帧发送帧1超时超时重发帧重发帧0超时超时重发帧重发帧1收到收到ACK（0）发送帧发送帧0收到收到NAK（0）重发帧重发帧0收到收到NAK（1）重发帧重发帧1 状态状态 事件事件动作动作收到收到ACK（1）或）或 NAK（1）超时超时收到收到ACK（0）或或 NAK（0）准备发送帧准备发送帧1处理处理发送帧发送帧1重发帧重发帧0重发帧重发帧0下一状态下一状态准备发送帧准备发送帧0/准备发送帧准备发送帧0处理处理重发帧重发帧1重发帧重发帧1发送帧发送帧0下一状态下一状态/准备发送帧准备发送帧1fsm程序框架程序框架n根据状态转

45、移表形成根据状态转移表形成fsm程序可能的框架程序可能的框架fsm( 当前状态当前状态,事件事件 ）switch( 事件）事件）case 事件事件1:case 事件事件2default：ignore；return next_state;action 1;next_state = xxx;main() state = initial; while(1) waite for a event; state = fsm(state,event); fsm.cif（当前状态（当前状态=X）用用FSM方式编程的网络仿真软件方式编程的网络仿真软件Optimized Network Engineering T

46、ools (OPNET) A three layer modeling hierarchy Network ModelNode Model用用FSM方式编程的网络仿真软件方式编程的网络仿真软件Node ModelP r o c e s s ModelProcess Model有限状态机对协议的验证有限状态机对协议的验证n对协议可靠性的验证对协议可靠性的验证n协议是否有死锁协议是否有死锁n协议是否有不正确的状态转换协议是否有不正确的状态转换n对可达性的验证对可达性的验证n是否有不可达的状态（无效状态）是否有不可达的状态（无效状态）n是否有效状态都可达是否有效状态都可达n验证协议需要从系统的角度去考虑验证协议需要从系统的角度去考虑n发送方、接收方、信道发送方、接收方、信道有限状态机对协议的验证有限状态机对协议的验证n以停等协议为例讨论以停等协议为例讨论n如何从系统的角度考虑变量和状态如何从系统的角度考虑变量和状态n如何确定有效状态如何确定有效状态n验证可达性验证可达性n如何验证协议死锁如何验证协议死锁n如何验证协议失败如何验证协议失败停等协议的变量与状态停等协议的变量与状态n变量变量（3个变量个变量XYZ）n发送方变量发送方变量Xn接收方变量接收方变量Yn信道变量（半双工）信道变量（半双工）Zn状态状态n所有变量的各种组合所有变量的各种组合n任何时刻