《計(jì)算機(jī)通信網(wǎng)》第3章數(shù)據(jù)鏈路層Part2

1、作業(yè)作業(yè)41、請(qǐng)寫(xiě)出通常采用的成幀方法及各種成幀法的特、請(qǐng)寫(xiě)出通常采用的成幀方法及各種成幀法的特點(diǎn)。假設(shè)幀標(biāo)記符出錯(cuò)，請(qǐng)問(wèn)哪種成幀方法將點(diǎn)。假設(shè)幀標(biāo)記符出錯(cuò)，請(qǐng)問(wèn)哪種成幀方法將不能檢測(cè)到后續(xù)所有的幀？為什么？不能檢測(cè)到后續(xù)所有的幀？為什么？2、如果待傳數(shù)據(jù)為、如果待傳數(shù)據(jù)為 1111111000111111，假，假設(shè)采用設(shè)采用“位填充法位填充法”成幀，請(qǐng)寫(xiě)出幀內(nèi)容。成幀，請(qǐng)寫(xiě)出幀內(nèi)容。3、假設(shè)待傳數(shù)據(jù)為、假設(shè)待傳數(shù)據(jù)為 100101，（，（1）計(jì)算校驗(yàn)位）計(jì)算校驗(yàn)位r的位數(shù)；（的位數(shù)；（2）計(jì)算出傳輸該數(shù)據(jù)的海明碼）計(jì)算出傳輸該數(shù)據(jù)的海明碼（要求步驟）（要求步驟）4、假設(shè)待傳數(shù)據(jù)為、假設(shè)待傳數(shù)

2、據(jù)為100101，采用，采用CRC編碼，假編碼，假設(shè)生成多項(xiàng)式為設(shè)生成多項(xiàng)式為G（X）=X4+1，計(jì)算出校驗(yàn)，計(jì)算出校驗(yàn)多項(xiàng)式多項(xiàng)式R（X）。）。3.4 差錯(cuò)與流量控制協(xié)議差錯(cuò)與流量控制協(xié)議n在計(jì)算機(jī)網(wǎng)絡(luò)中，差錯(cuò)控制方式通常采用在計(jì)算機(jī)網(wǎng)絡(luò)中，差錯(cuò)控制方式通常采用 自動(dòng)請(qǐng)求重發(fā)（自動(dòng)請(qǐng)求重發(fā)（ARQ ）nARQ基本思想：基本思想：n采用檢錯(cuò)碼進(jìn)行檢錯(cuò)采用檢錯(cuò)碼進(jìn)行檢錯(cuò)n丟棄出錯(cuò)的幀丟棄出錯(cuò)的幀n請(qǐng)求重傳出錯(cuò)的幀請(qǐng)求重傳出錯(cuò)的幀n對(duì)幀進(jìn)行確認(rèn)對(duì)幀進(jìn)行確認(rèn)n典型的典型的ARQ協(xié)議協(xié)議n停等協(xié)議停等協(xié)議n回退回退N協(xié)議協(xié)議n選擇性重傳協(xié)議選擇性重傳協(xié)議nARQ是一種保證是一種保證PDU可靠傳輸?shù)募夹g(shù)

3、可靠傳輸?shù)募夹g(shù)n可用于各層協(xié)議中，不僅僅限于數(shù)據(jù)鏈路層可用于各層協(xié)議中，不僅僅限于數(shù)據(jù)鏈路層n 例如：例如：nX.25網(wǎng)絡(luò)的網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層網(wǎng)絡(luò)的網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層nTCP/IP網(wǎng)絡(luò)中的傳送層網(wǎng)絡(luò)中的傳送層3.4 差錯(cuò)與流量控制協(xié)議差錯(cuò)與流量控制協(xié)議n3.4.1 停停等協(xié)議等協(xié)議n3.4.2 連續(xù)發(fā)送的滑動(dòng)窗口協(xié)議的概念連續(xù)發(fā)送的滑動(dòng)窗口協(xié)議的概念n3.4.3 回退回退N協(xié)議協(xié)議n3.4.4 選擇性重傳協(xié)議選擇性重傳協(xié)議n3.4.4 雙向傳輸時(shí)的確認(rèn)雙向傳輸時(shí)的確認(rèn)n3.4.4 流量控制流量控制3.4.1停停等協(xié)議等協(xié)議n停停等協(xié)議：等協(xié)議：stop and wait protocoln基本

4、思想：基本思想：n每發(fā)送一個(gè)每發(fā)送一個(gè)幀（幀（PDU），），停下來(lái)等確認(rèn)（應(yīng)答）停下來(lái)等確認(rèn)（應(yīng)答）n收到肯定應(yīng)答，發(fā)送下一個(gè)新幀（收到肯定應(yīng)答，發(fā)送下一個(gè)新幀（PDU）n收到否定應(yīng)答，重發(fā)上次的幀收到否定應(yīng)答，重發(fā)上次的幀 ACK新新PDUNAKDATADATA新新PDUDATA網(wǎng)網(wǎng)絡(luò)絡(luò)層層鏈路層鏈路層鏈路層鏈路層網(wǎng)網(wǎng)絡(luò)絡(luò)層層重發(fā)重發(fā)PDUDATAACKl 數(shù)據(jù)鏈路層的數(shù)據(jù)鏈路層的 PDU也稱(chēng)為幀也稱(chēng)為幀l 后續(xù)討論中幀后續(xù)討論中幀 和和PDU等同等同3.4.1停停等協(xié)議等協(xié)議 協(xié)議需要考慮以下情況協(xié)議需要考慮以下情況n幀丟失，將導(dǎo)致：幀丟失，將導(dǎo)致：n接收方收不到接收方收不到PDUn發(fā)送方

5、收不到應(yīng)答（發(fā)送方收不到應(yīng)答（ACK或或NAK）n應(yīng)答丟失，將導(dǎo)致：應(yīng)答丟失，將導(dǎo)致：n發(fā)送方收不到應(yīng)答（發(fā)送方收不到應(yīng)答（ACK或或NAK）n解決辦法：設(shè)置定時(shí)器解決辦法：設(shè)置定時(shí)器T，超時(shí)重發(fā)，超時(shí)重發(fā)PDUPDUACKTPDUPDUACKT重傳重傳重傳重傳3.4.1停停等協(xié)議等協(xié)議n還有問(wèn)題要解決：還有問(wèn)題要解決：n連續(xù)丟失問(wèn)題連續(xù)丟失問(wèn)題n重發(fā)后仍收不到應(yīng)答或接收方仍收不到重發(fā)后仍收不到應(yīng)答或接收方仍收不到PDU，一直重發(fā)下去？，一直重發(fā)下去？n解決辦法：設(shè)置重發(fā)次數(shù)解決辦法：設(shè)置重發(fā)次數(shù)Nmaxn重復(fù)收幀問(wèn)題重復(fù)收幀問(wèn)題nACK丟失，重發(fā)丟失，重發(fā)PDU，接收方收到重復(fù)幀而不知道，接

6、收方收到重復(fù)幀而不知道n措施：為措施：為PDU編號(hào)（編號(hào)（0 1即可區(qū)別）即可區(qū)別）重復(fù)重復(fù)PDU丟棄丟棄PDU（0）PDU（0）ACKT重傳重傳PDU有編號(hào)有編號(hào)不出錯(cuò)不出錯(cuò)PDUPDUACKT重傳重傳新新PDU？PDU無(wú)編號(hào)無(wú)編號(hào)會(huì)出錯(cuò)會(huì)出錯(cuò)3.4.1停停等協(xié)議等協(xié)議n還有問(wèn)題要解決：還有問(wèn)題要解決：n過(guò)早超時(shí)問(wèn)題過(guò)早超時(shí)問(wèn)題n重發(fā)定時(shí)器重發(fā)定時(shí)器T在應(yīng)答到達(dá)發(fā)送方之前就超時(shí)在應(yīng)答到達(dá)發(fā)送方之前就超時(shí)n導(dǎo)致接收方正確收到導(dǎo)致接收方正確收到PDU，而發(fā)送方仍然重發(fā)，而發(fā)送方仍然重發(fā)n如果過(guò)早超時(shí)，且如果過(guò)早超時(shí)，且ACK無(wú)編號(hào)，則無(wú)編號(hào)，則n出現(xiàn)發(fā)送出現(xiàn)發(fā)送PDU出錯(cuò)出錯(cuò)n措施：對(duì)應(yīng)答編號(hào)措

7、施：對(duì)應(yīng)答編號(hào)n請(qǐng)同學(xué)自己分析以下情況：請(qǐng)同學(xué)自己分析以下情況：n過(guò)早超時(shí)，但過(guò)早超時(shí)，但PDU和和ACK都編號(hào)時(shí)，都編號(hào)時(shí)， 停等協(xié)議將如何工作？停等協(xié)議將如何工作？重復(fù)重復(fù)PDU丟棄丟棄PDU（0）PDU（0）ACKT重傳重傳PDU（1）ACKPDU（0）發(fā)送方誤以為是對(duì)發(fā)送方誤以為是對(duì)PDU（1）的應(yīng)答，故下一）的應(yīng)答，故下一個(gè)發(fā)個(gè)發(fā)PDU（0） 出錯(cuò)！出錯(cuò)！數(shù)據(jù)幀編號(hào)數(shù)據(jù)幀編號(hào)DUDUN校驗(yàn)校驗(yàn)TDUDUN校驗(yàn)校驗(yàn)TIf(N=Vr)Vr+;N=VsVs+;對(duì)對(duì)DU順序編號(hào)順序編號(hào)DU順序提交上層順序提交上層發(fā)送變量發(fā)送變量Vs實(shí)現(xiàn)實(shí)現(xiàn)對(duì)對(duì)DU的順序編號(hào)的順序編號(hào)接收變量接收變量Vr控制

8、控制DU的順序提交的順序提交DUN校驗(yàn)校驗(yàn)TN=幀序號(hào)幀序號(hào),0,1,2,T=幀類(lèi)型，幀類(lèi)型，DATA，ACK，TQ(待發(fā)送隊(duì)列待發(fā)送隊(duì)列)記為記為Fm(N)Fm(N)數(shù)據(jù)封裝實(shí)現(xiàn)數(shù)據(jù)封裝實(shí)現(xiàn)(擴(kuò))n用用skbBuff實(shí)現(xiàn)實(shí)現(xiàn)MAC實(shí)體實(shí)體IP實(shí)體實(shí)體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實(shí)體實(shí)體DataLenDataPosskbPush(pPDU,len)lenskbGetDataPtr(pPDU)SAPSAP數(shù)據(jù)幀編號(hào)數(shù)據(jù)幀編號(hào)(擴(kuò))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、;超時(shí)重傳超時(shí)重傳TQ取出一幀發(fā)送取出一幀發(fā)送送入重傳隊(duì)列送入重傳隊(duì)列TimerStartTimer等待應(yīng)答等待應(yīng)答RTQStopTimer應(yīng)答到應(yīng)答到取出一幀發(fā)送取出一幀發(fā)送TimeOutStartTimer重傳隊(duì)列重傳隊(duì)列WaitACK() int Retry=0； while(1) event = WaitEvent(); / 無(wú)事件時(shí)，阻塞軟件執(zhí)行無(wú)事件時(shí)，阻塞軟件執(zhí)行 switch(event) case T0: pSkb=GetEntry(RTQ);/ 從隊(duì)列中獲得但不取出從隊(duì)列中獲得但不取出 SendFrame(pSkb); StartTimer(T0); Retry+; if

12、(ReTry = MaxTry) return -1; break; case ACK: pSkb = DeQue(RTQ); skbFree(pSkb); StopTimer(T0); return 0; break; 超時(shí)重傳（擴(kuò)）超時(shí)重傳（擴(kuò)）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幀協(xié)議（幀協(xié)議（Go back n）n是一個(gè)發(fā)送窗口為是一個(gè)發(fā)送窗口為Ws，接收窗口為，接收窗口為1的滑動(dòng)窗口協(xié)議的滑動(dòng)窗口協(xié)議 教材教材.n 基本思想基本思想n發(fā)送方發(fā)送方n一次可連續(xù)發(fā)送多個(gè)一次可連續(xù)發(fā)送多個(gè)PDUn始終維持未應(yīng)答的始終維持未應(yīng)答的PDU個(gè)數(shù)某一個(gè)值（發(fā)送窗口大?。﹤€(gè)數(shù)某一個(gè)值（發(fā)送窗口大?。﹏超時(shí)重發(fā)窗口未被確認(rèn)的所有超時(shí)重發(fā)窗口未被確認(rèn)的所有PDU（回退（回退n）n接收方接收方n一個(gè)一個(gè)地按序收一個(gè)一個(gè)地按序收PDUn序號(hào)及內(nèi)容正確的序號(hào)及內(nèi)容正確的PDU，數(shù)據(jù)上交上層，數(shù)據(jù)上交上層

14、n出錯(cuò)的出錯(cuò)的PDU及后續(xù)（非期望）的及后續(xù)（非期望）的PDU全部丟棄。全部丟棄。 n要求：要求：n發(fā)送緩沖區(qū)為發(fā)送緩沖區(qū)為Ws個(gè)個(gè)n接收緩沖區(qū)為接收緩沖區(qū)為13.4.3 回退回退n幀協(xié)議（幀協(xié)議（Go back n） 發(fā)送窗口滑動(dòng)舉例發(fā)送窗口滑動(dòng)舉例n假設(shè)；用假設(shè)；用3位二進(jìn)制對(duì)位二進(jìn)制對(duì)PDU編號(hào)，發(fā)送窗口編號(hào)，發(fā)送窗口 Ws=4 PDU編號(hào)為編號(hào)為0、17循環(huán)使用循環(huán)使用n假設(shè)：已連續(xù)發(fā)送了假設(shè)：已連續(xù)發(fā)送了03號(hào)號(hào)PDU，等應(yīng)答，等應(yīng)答 則：則： 窗口內(nèi)的窗口內(nèi)的PDU為為0-3號(hào)號(hào)n如收到如收到ACK（2），則），則n將窗口底部移到將窗口底部移到2，窗口頂部向前移，保持窗口大小為，窗

15、口頂部向前移，保持窗口大小為Ws=4，此時(shí)新窗口內(nèi)的，此時(shí)新窗口內(nèi)的PDU為為2、3、4、524670135012345673.4.3 回退回退n幀協(xié)議（幀協(xié)議（Go back n）假設(shè)假設(shè)PDU編號(hào)為編號(hào)為3位二進(jìn)制數(shù)，位二進(jìn)制數(shù)，Ws=4每幀確認(rèn)，每幀確認(rèn)，ACK（K）表示希望收下一個(gè)）表示希望收下一個(gè)PDU（K）5601245601234超時(shí)超時(shí)5346丟棄丟棄7120573460ACK（3）收到收到PDU（2）下一個(gè)收下一個(gè)收PDU（3）回退整個(gè)窗回退整個(gè)窗口，重發(fā)口，重發(fā)3.4.3 回退回退n幀協(xié)議（幀協(xié)議（Go back n） 協(xié)議運(yùn)行原理協(xié)議運(yùn)行原理n發(fā)送方發(fā)送方n窗口尺寸：窗口

16、尺寸：1Ws2N-1，最多連續(xù)發(fā)送窗口中的，最多連續(xù)發(fā)送窗口中的Ws個(gè)個(gè)PDUn窗口滑動(dòng)：收到期望的窗口滑動(dòng)：收到期望的Ack(k)：窗口底部移到：窗口底部移到 PDU（k），窗口頂部向前移動(dòng)，始終保持窗口里有），窗口頂部向前移動(dòng)，始終保持窗口里有Ws個(gè)個(gè)PDU未確認(rèn)未確認(rèn)n窗口滑動(dòng)后，發(fā)送新進(jìn)入窗口的窗口滑動(dòng)后，發(fā)送新進(jìn)入窗口的PDUn超時(shí)重發(fā)：超時(shí)重發(fā)： 超過(guò)超過(guò)T未收到期望的未收到期望的Ack，重發(fā)窗口中的，重發(fā)窗口中的PDU(回退整個(gè)窗口回退整個(gè)窗口)n超次數(shù)失?。撼^(guò)最大重發(fā)次數(shù)超次數(shù)失敗：超過(guò)最大重發(fā)次數(shù)Nmax仍無(wú)正確應(yīng)答仍無(wú)正確應(yīng)答3.4.3 回退回退n幀協(xié)議（幀協(xié)議（Go b

17、ack n） 協(xié)議運(yùn)行原理協(xié)議運(yùn)行原理n接收方接收方n窗口尺寸：窗口尺寸：Wr=1n按序接收：按照按序接收：按照PDU編號(hào)依序接收，出錯(cuò)、亂序編號(hào)依序接收，出錯(cuò)、亂序PDU一一律丟棄律丟棄n確認(rèn)含義：確認(rèn)含義：Ack(k)表示對(duì)表示對(duì)k-1及以前各編號(hào)的及以前各編號(hào)的PDU的確的確認(rèn)，同時(shí)期望接收第認(rèn)，同時(shí)期望接收第k號(hào)號(hào)PDUn確認(rèn)策略：確認(rèn)策略： 按序到達(dá)的按序到達(dá)的PDU可立即確認(rèn)，也可延遲確認(rèn)可立即確認(rèn)，也可延遲確認(rèn)(收到多幀后一起確認(rèn)收到多幀后一起確認(rèn))，但出錯(cuò)或亂序的，但出錯(cuò)或亂序的PDU，確認(rèn)，確認(rèn)Ack(k)（期望接收（期望接收k號(hào)號(hào)PDU）或不應(yīng)答）或不應(yīng)答3.4.3 回退回

18、退n幀協(xié)議（幀協(xié)議（Go back n）如果如果Ws 2N，會(huì)出現(xiàn)什么情況？，會(huì)出現(xiàn)什么情況？（協(xié)議會(huì)失?。。▍f(xié)議會(huì)失?。。┘僭O(shè)：假設(shè)：N=2，則，則PDU為為0-3號(hào)（號(hào)（4個(gè)）循環(huán)使用個(gè)）循環(huán)使用超時(shí)超時(shí)2013201320132013重復(fù)，無(wú)法分辨重復(fù)，無(wú)法分辨ACK（0）希望下一個(gè)收希望下一個(gè)收PDU（0）Ws=4，協(xié)議失敗，協(xié)議失敗超時(shí)超時(shí)201201201201重復(fù)，丟棄重復(fù)，丟棄ACK（3）希望下一個(gè)收希望下一個(gè)收PDU（3）Ws=34 ,則協(xié)議運(yùn)行正常則協(xié)議運(yùn)行正常3.4.3 回退回退n幀協(xié)議幀協(xié)議nSelect the go back Number Nn發(fā)送發(fā)送PDUi時(shí)，

19、繼續(xù)發(fā)送后續(xù)的時(shí)，繼續(xù)發(fā)送后續(xù)的PDU，直到，直到“預(yù)期預(yù)期”收收到到ACKi+1的時(shí)刻為止的時(shí)刻為止n可持續(xù)發(fā)送可持續(xù)發(fā)送N個(gè)個(gè)PDU：PDUi . PDUi+N-1n發(fā)送序號(hào)超前應(yīng)答序號(hào)發(fā)送序號(hào)超前應(yīng)答序號(hào)N2 tN1+ t2 3.4.4 選擇性重傳協(xié)議選擇性重傳協(xié)議（selective repeat）n發(fā)送窗口為發(fā)送窗口為Ws，接收窗口為，接收窗口為Wr的滑動(dòng)窗口協(xié)議的滑動(dòng)窗口協(xié)議 教材教材.3n 基本思想基本思想n改進(jìn)回退改進(jìn)回退n幀協(xié)議由于一個(gè)幀協(xié)議由于一個(gè)PDU錯(cuò)，需重傳后續(xù)多個(gè)錯(cuò)，需重傳后續(xù)多個(gè)PDU的問(wèn)題的問(wèn)題n發(fā)送方發(fā)送方n對(duì)應(yīng)一個(gè)發(fā)送窗口，可連續(xù)發(fā)送窗口內(nèi)的多個(gè)對(duì)應(yīng)一個(gè)發(fā)送

20、窗口，可連續(xù)發(fā)送窗口內(nèi)的多個(gè)PDU，并保持未被確認(rèn)的，并保持未被確認(rèn)的PDU個(gè)數(shù)為窗口值個(gè)數(shù)為窗口值n只重發(fā)接收方指定序號(hào)的只重發(fā)接收方指定序號(hào)的PDU或超時(shí)的或超時(shí)的PDUn接收方接收方n也對(duì)應(yīng)一個(gè)接收窗口，接收序號(hào)落在窗口內(nèi)的也對(duì)應(yīng)一個(gè)接收窗口，接收序號(hào)落在窗口內(nèi)的PDU，存儲(chǔ)出錯(cuò)的后續(xù)，存儲(chǔ)出錯(cuò)的后續(xù)PDU及亂序的及亂序的PDUn窗口外窗口外PDU一律丟棄，指定需重發(fā)的一律丟棄，指定需重發(fā)的PDU，排序并按序上交數(shù)據(jù)，排序并按序上交數(shù)據(jù)n要求：要求：n發(fā)送緩沖區(qū)為發(fā)送緩沖區(qū)為Ws個(gè)個(gè)n接收緩沖區(qū)為接收緩沖區(qū)為Wr個(gè)個(gè)3.4.4選擇性重傳協(xié)議選擇性重傳協(xié)議n除正常的應(yīng)答除正常的應(yīng)答ACK（

21、K）外，增加一個(gè)否定應(yīng)答）外，增加一個(gè)否定應(yīng)答NAK（K），兩者含義不同：），兩者含義不同：nACK（K）：表示收方已正確收到）：表示收方已正確收到K-1及以前所有及以前所有的的PDU，希望下一個(gè)接收，希望下一個(gè)接收K號(hào)號(hào)PDU，K號(hào)及后續(xù)的號(hào)及后續(xù)的PDU一定還未收到一定還未收到nNAK（K）：表示第）：表示第K號(hào)號(hào)PDU出錯(cuò)或丟失，但出錯(cuò)或丟失，但K號(hào)號(hào)前的所有前的所有PDU收到，希望重發(fā)第收到，希望重發(fā)第K號(hào)號(hào)PDU，還隱含，還隱含K號(hào)以后的后續(xù)號(hào)以后的后續(xù)PDU可能已收到，只等可能已收到，只等PDU（K）的到來(lái)，重新排序后便可按序上交的到來(lái)，重新排序后便可按序上交3.4.4選擇性重傳協(xié)

22、議選擇性重傳協(xié)議 協(xié)議運(yùn)行原理協(xié)議運(yùn)行原理n發(fā)送方發(fā)送方n窗口尺寸：窗口尺寸：1Ws2N/2，最多連續(xù)發(fā)送窗口中的，最多連續(xù)發(fā)送窗口中的Ws個(gè)個(gè)PDUn窗口滑動(dòng)：與回退窗口滑動(dòng)：與回退n幀協(xié)議相同幀協(xié)議相同n選擇重發(fā)：收到選擇重發(fā)：收到NAK（K），重發(fā)），重發(fā)PDU（K）n超時(shí)重發(fā)：超過(guò)超時(shí)重發(fā)：超過(guò)T未收到期望的未收到期望的ACK，重發(fā)當(dāng)前超時(shí)未應(yīng)，重發(fā)當(dāng)前超時(shí)未應(yīng)答的答的PDUn超次數(shù)失?。撼^(guò)最大重發(fā)次數(shù)超次數(shù)失?。撼^(guò)最大重發(fā)次數(shù)Nmax仍無(wú)正確應(yīng)答，仍無(wú)正確應(yīng)答，報(bào)告上層失敗報(bào)告上層失敗3.4.4選擇性重傳協(xié)議選擇性重傳協(xié)議 協(xié)議運(yùn)行原理協(xié)議運(yùn)行原理n接收方接收方n窗口尺寸：窗口尺

23、寸：12N，會(huì)出現(xiàn)什么情況？會(huì)出現(xiàn)什么情況？（協(xié)議會(huì)失?。。▍f(xié)議會(huì)失敗?。┘僭O(shè)：假設(shè)：N=2，則，則PDU為為0-3號(hào)（號(hào)（4個(gè)）循環(huán)使用個(gè)）循環(huán)使用Ws=3，Wr=2 協(xié)議失敗協(xié)議失敗201200121012重復(fù)重復(fù)0不能辨認(rèn)不能辨認(rèn)ACK（3）ACK（1）超時(shí)超時(shí)NAK（3）n Ws初始為：初始為：0，1，2n Wr初始為：初始為：0，1，正確收到，正確收到0和和1幀，幀， 發(fā)發(fā)ACK，窗口變?yōu)椋?，窗口變?yōu)椋?，3n 收到收到PDU（2），發(fā)），發(fā)ACK（3），）， 窗口為：窗口為：3，0，所有，所有3個(gè)應(yīng)答均丟失。個(gè)應(yīng)答均丟失。 n 發(fā)端超時(shí)重發(fā)均超時(shí)的發(fā)端超時(shí)重發(fā)均超時(shí)的PDU（0）

24、 PDU（2），而），而PDU（0）在接收新窗）在接收新窗口內(nèi)，收端不知是重發(fā)，當(dāng)作新數(shù)據(jù)存起口內(nèi)，收端不知是重發(fā)，當(dāng)作新數(shù)據(jù)存起來(lái)，發(fā)來(lái)，發(fā)NAK（3）3.4.5 雙向傳輸時(shí)的確認(rèn)雙向傳輸時(shí)的確認(rèn)n雙向數(shù)據(jù)傳輸雙向數(shù)據(jù)傳輸n獨(dú)立保證每個(gè)方向的傳輸可靠性獨(dú)立保證每個(gè)方向的傳輸可靠性n站點(diǎn)間一般只有一對(duì)雙向信道站點(diǎn)間一般只有一對(duì)雙向信道發(fā)送方發(fā)送方接收方接收方接收方接收方發(fā)送方發(fā)送方Link-ALink-B發(fā)送方發(fā)送方接收方接收方接收方接收方發(fā)送方發(fā)送方Link-ALink-B兩對(duì)雙向信道上實(shí)現(xiàn)兩對(duì)雙向信道上實(shí)現(xiàn) 可得到及時(shí)應(yīng)答可得到及時(shí)應(yīng)答 應(yīng)答信道利用不充分應(yīng)答信道利用不充分一對(duì)雙向信道上實(shí)

25、現(xiàn)一對(duì)雙向信道上實(shí)現(xiàn) 數(shù)據(jù)和應(yīng)答在時(shí)間上相互影響數(shù)據(jù)和應(yīng)答在時(shí)間上相互影響 雙向信道都能充分利用雙向信道都能充分利用3.4.5 雙向傳輸時(shí)的確認(rèn)雙向傳輸時(shí)的確認(rèn)n捎帶確認(rèn)捎帶確認(rèn)發(fā)送方發(fā)送方接收方接收方接收方接收方發(fā)送方發(fā)送方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站點(diǎn)維持兩個(gè)變量站點(diǎn)維持兩個(gè)變量Vs和和Vr Vs控制發(fā)送，控制發(fā)送，Vr控制接收控制接收

26、注意：注意： Vs和和Vr的值是相互獨(dú)立的的值是相互獨(dú)立的Fm(2,4)Fm(3,4)Fm(Ns=Vs, Nr=Vr)Fm(4,2)Fm(4,3)3.4.6 流量控制流量控制n流控問(wèn)題流控問(wèn)題n當(dāng)接收方因某種原因暫時(shí)無(wú)法接收數(shù)據(jù)幀時(shí)當(dāng)接收方因某種原因暫時(shí)無(wú)法接收數(shù)據(jù)幀時(shí)n是不應(yīng)答發(fā)送方，讓發(fā)送方超時(shí)重發(fā)來(lái)緩解是不應(yīng)答發(fā)送方，讓發(fā)送方超時(shí)重發(fā)來(lái)緩解n若不應(yīng)答時(shí)間過(guò)長(zhǎng)，可能造成發(fā)送方多次重發(fā)后放棄通信若不應(yīng)答時(shí)間過(guò)長(zhǎng)，可能造成發(fā)送方多次重發(fā)后放棄通信n發(fā)送方似乎應(yīng)該暫停這種無(wú)謂的重發(fā)發(fā)送方似乎應(yīng)該暫停這種無(wú)謂的重發(fā)n應(yīng)該采用某種機(jī)制，通知發(fā)送方暫停應(yīng)該采用某種機(jī)制，通知發(fā)送方暫停Fm(i)Fm(i

27、)不應(yīng)答不應(yīng)答不應(yīng)答不應(yīng)答流量控制流量控制n流控技術(shù)流控技術(shù)n定義新的應(yīng)答幀定義新的應(yīng)答幀RNR(Nr), Receive Not ReadynNr表示：表示：Nr-1號(hào)幀已收到，期望但暫停號(hào)幀已收到，期望但暫停Nr號(hào)幀發(fā)送號(hào)幀發(fā)送n當(dāng)接收方需要暫停接收時(shí)當(dāng)接收方需要暫停接收時(shí)n向發(fā)送方發(fā)向發(fā)送方發(fā)RNR(Nr)n發(fā)送方暫停等待，而不是超時(shí)重發(fā)發(fā)送方暫停等待，而不是超時(shí)重發(fā)n當(dāng)接收方可繼續(xù)接收時(shí)當(dāng)接收方可繼續(xù)接收時(shí)n向發(fā)送方發(fā)送除向發(fā)送方發(fā)送除RNR外其他的應(yīng)答幀外其他的應(yīng)答幀(Nr)nNr表示期望的幀序號(hào)表示期望的幀序號(hào)n發(fā)送方解除暫停狀態(tài)，繼續(xù)幀序列的發(fā)送發(fā)送方解除暫停狀態(tài)，繼續(xù)幀序列的發(fā)

28、送Fm(i)RNR(i+1)暫停發(fā)送暫停發(fā)送ACK(i+1)Fm(i+1)流量控制流量控制n流量控制流量控制流量控制是避免快的發(fā)送方淹沒(méi)慢的接收方，使收發(fā)速率流量控制是避免快的發(fā)送方淹沒(méi)慢的接收方，使收發(fā)速率適配適配常用的流量控制方法：常用的流量控制方法：方法方法1：接收方緩存快滿(mǎn)時(shí)，向發(fā)送方發(fā)送一個(gè)流控消息：接收方緩存快滿(mǎn)時(shí)，向發(fā)送方發(fā)送一個(gè)流控消息 告知自己暫時(shí)不能接收告知自己暫時(shí)不能接收PDU ，有空間后再通知對(duì)，有空間后再通知對(duì) 方繼續(xù)（方繼續(xù)（HDLC采用）采用）方法方法2：直接關(guān)閉接收窗口（：直接關(guān)閉接收窗口（TCP采用）采用）ARQ協(xié)議小結(jié)協(xié)議小結(jié)n差錯(cuò)控制基本方法差錯(cuò)控制基本方

29、法對(duì)對(duì)PDU編號(hào)編號(hào)存儲(chǔ)未確認(rèn)的存儲(chǔ)未確認(rèn)的PDU以便對(duì)以便對(duì)PDU重發(fā)重發(fā)接收接收方對(duì)方對(duì)PDU確認(rèn)確認(rèn)對(duì)正確的對(duì)正確的PDU發(fā)發(fā)ACK 策略策略1： ACK（K），對(duì)），對(duì)K及之前序號(hào)的確認(rèn)，希望及之前序號(hào)的確認(rèn)，希望 收收 K+1號(hào)號(hào)策略策略2(超前應(yīng)答超前應(yīng)答) ： ACK（K），對(duì)），對(duì)K-1及之前序號(hào)的及之前序號(hào)的確認(rèn)，希望收確認(rèn)，希望收K號(hào)號(hào)對(duì)錯(cuò)誤的對(duì)錯(cuò)誤的PDU發(fā)發(fā)NAK或什么也不發(fā)或什么也不發(fā)可能稍帶確認(rèn)可能稍帶確認(rèn)發(fā)送方觸發(fā)送方觸發(fā)重發(fā)發(fā)重發(fā)對(duì)每個(gè)已發(fā)對(duì)每個(gè)已發(fā)PDU設(shè)置計(jì)時(shí)器，超時(shí)未收到確認(rèn)，則重發(fā)設(shè)置計(jì)時(shí)器，超時(shí)未收到確認(rèn)，則重發(fā)對(duì)收到對(duì)收到NAK的的PDU重發(fā)重發(fā)重發(fā)

30、內(nèi)容：重發(fā)內(nèi)容： 回退回退N：重發(fā)窗口內(nèi)所有：重發(fā)窗口內(nèi)所有PDU 選擇性重發(fā)：只重發(fā)超時(shí)的和選擇性重發(fā)：只重發(fā)超時(shí)的和NAK的的PDUARQ協(xié)議小結(jié)協(xié)議小結(jié)nPDU的編號(hào)（循環(huán)使用）的編號(hào)（循環(huán)使用）n停等協(xié)議停等協(xié)議n1位二進(jìn)制數(shù)表示，編號(hào)為位二進(jìn)制數(shù)表示，編號(hào)為0、1兩個(gè)兩個(gè)n回退回退N和選擇性重傳：和選擇性重傳：nN位二進(jìn)制數(shù)表示，編號(hào)為位二進(jìn)制數(shù)表示，編號(hào)為0，1 . 2N-1n窗口大小窗口大小n停等協(xié)議：停等協(xié)議：n發(fā)送窗口發(fā)送窗口Ws=接收窗口接收窗口Wr=1 n回退回退N協(xié)議：協(xié)議：n 1Ws2N-1，Wr=1 注意：注意： Ws不能等于不能等于2N（PDU最大序號(hào)數(shù)最大序號(hào)數(shù)

31、+1）n選擇性重傳協(xié)議：選擇性重傳協(xié)議：n1Ws2N/2， 1Wr2N/2 注意實(shí)際的條件：注意實(shí)際的條件：Ws+Wr不能大于不能大于2Nn提醒：提醒：Ws與與Wr并無(wú)直接關(guān)系并無(wú)直接關(guān)系n緩存大小緩存大小n與窗口大小一致。與窗口大小一致。注意：不是與注意：不是與PDU的個(gè)數(shù)一致的個(gè)數(shù)一致3.5 協(xié)議描述和驗(yàn)證協(xié)議描述和驗(yàn)證n為什么要描述協(xié)議？為什么要描述協(xié)議？引入：協(xié)議的描述方法引入：協(xié)議的描述方法xn協(xié)議規(guī)范通常采用自然語(yǔ)言協(xié)議規(guī)范通常采用自然語(yǔ)言易閱讀，但不嚴(yán)格和精確，理解上易出現(xiàn)二義性易閱讀，但不嚴(yán)格和精確，理解上易出現(xiàn)二義性 文檔文檔RFCxxxx 文檔的一般格式文檔的一般格式n時(shí)序

32、圖時(shí)序圖直觀，但零散只針對(duì)特殊情況直觀，但零散只針對(duì)特殊情況Introduction Glossary Content OverviewBodyReference時(shí)序圖的一般格式時(shí)序圖的一般格式connection_request( )connection_indication( )connection_response( )connection_confirmation( )N+1NN+1SABMEUAt上下層實(shí)上下層實(shí)體間接口體間接口上下層實(shí)上下層實(shí)體間事件體間事件對(duì)等層實(shí)對(duì)等層實(shí)體間事件體間事件N對(duì)等層對(duì)等層對(duì)等層對(duì)等層時(shí)間時(shí)間描述方式直觀描述方式直觀但過(guò)于零散但過(guò)于零散協(xié)議描述和驗(yàn)證協(xié)

33、議描述和驗(yàn)證n時(shí)序圖描述時(shí)序圖描述如此的時(shí)間圖僅能描述雙方配合的某些特例，如此的時(shí)間圖僅能描述雙方配合的某些特例，難以描述所有可能出現(xiàn)的情況。否則，設(shè)計(jì)難以描述所有可能出現(xiàn)的情況。否則，設(shè)計(jì)協(xié)議軟件的人會(huì)問(wèn)：協(xié)議軟件的人會(huì)問(wèn)：如果雙方都同時(shí)向?qū)Ψ桨l(fā)送如果雙方都同時(shí)向?qū)Ψ桨l(fā)送SARM該如何處理？該如何處理？如果雙方的應(yīng)答有一個(gè)丟失了，怎么辦？如果雙方的應(yīng)答有一個(gè)丟失了，怎么辦？如果一方發(fā)送數(shù)據(jù)，另一方卻回到如果一方發(fā)送數(shù)據(jù)，另一方卻回到closed,怎么辦？怎么辦？如果一方發(fā)送數(shù)據(jù)時(shí)又收到對(duì)方的如果一方發(fā)送數(shù)據(jù)時(shí)又收到對(duì)方的SARM如何處理？如何處理？如果數(shù)據(jù)序號(hào)和應(yīng)答的序號(hào)差異太大，該如何處理

34、？如果數(shù)據(jù)序號(hào)和應(yīng)答的序號(hào)差異太大，該如何處理？ 協(xié)議應(yīng)該把這些配合過(guò)程都描述清楚，否則協(xié)議應(yīng)該把這些配合過(guò)程都描述清楚，否則協(xié)議是無(wú)法實(shí)現(xiàn)的，也不可能正常工作協(xié)議是無(wú)法實(shí)現(xiàn)的，也不可能正常工作!SARMUAF(0)RR(1)xTOF(0)3.5.1有限狀態(tài)機(jī)有限狀態(tài)機(jī)Finite State Machinen一種直觀、全局、準(zhǔn)確的協(xié)議描述方法一種直觀、全局、準(zhǔn)確的協(xié)議描述方法狀態(tài)狀態(tài)轉(zhuǎn)移轉(zhuǎn)移事件事件動(dòng)作動(dòng)作缺點(diǎn)缺點(diǎn)時(shí)序時(shí)序性不性不強(qiáng)強(qiáng)TCP協(xié)議的狀態(tài)機(jī)協(xié)議的狀態(tài)機(jī)有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSMn事件事件n來(lái)自實(shí)體外部，觸發(fā)實(shí)體產(chǎn)生動(dòng)作、改變狀態(tài)來(lái)自實(shí)體外部，觸發(fā)實(shí)體產(chǎn)生動(dòng)作、改變狀態(tài)n收到報(bào)文收

35、到報(bào)文(數(shù)據(jù)幀、應(yīng)答幀、定時(shí)器到等數(shù)據(jù)幀、應(yīng)答幀、定時(shí)器到等)n動(dòng)作動(dòng)作n實(shí)體對(duì)外部或內(nèi)部的操作實(shí)體對(duì)外部或內(nèi)部的操作n發(fā)送幀，滑動(dòng)窗口、改變狀態(tài)變量等操作發(fā)送幀，滑動(dòng)窗口、改變狀態(tài)變量等操作n狀態(tài)狀態(tài)n實(shí)體在一系列事件之間的記憶效應(yīng)實(shí)體在一系列事件之間的記憶效應(yīng)狀態(tài)狀態(tài)事件事件動(dòng)作動(dòng)作系統(tǒng)系統(tǒng)(有記憶效應(yīng)有記憶效應(yīng))激勵(lì)激勵(lì)響應(yīng)響應(yīng)對(duì)比：信號(hào)與系統(tǒng)對(duì)比：信號(hào)與系統(tǒng)e(t)h(s,t) (s=狀態(tài)狀態(tài))r(t)協(xié)議實(shí)體協(xié)議實(shí)體線(xiàn)性時(shí)不變系統(tǒng)線(xiàn)性時(shí)不變系統(tǒng)線(xiàn)性時(shí)變系統(tǒng)線(xiàn)性時(shí)變系統(tǒng)有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSMn事件、動(dòng)作、狀態(tài)事件、動(dòng)作、狀態(tài)Open發(fā)送發(fā)送(ConnReq)ConnACKClose

36、dReq SentReadyPacketWait發(fā)送發(fā)送F(0)RR(1)Ready1 0ClosedOpenReq sentConnReqConnACKReadyPacketF(0)WaitRR(1)Ready發(fā)送發(fā)送F(1)PacketF(1)WaitTime OutF(1)RR(0)RR(0)ReadyTime Out協(xié)議實(shí)體協(xié)議實(shí)體時(shí)間圖時(shí)間圖建立連接請(qǐng)求，等待應(yīng)答建立連接請(qǐng)求，等待應(yīng)答收到應(yīng)答，準(zhǔn)備通信收到應(yīng)答，準(zhǔn)備通信上層上層Packet, 發(fā)送，等待響應(yīng)發(fā)送，等待響應(yīng)收到正確應(yīng)答，準(zhǔn)備下一幀收到正確應(yīng)答，準(zhǔn)備下一幀等待超時(shí)，重發(fā)當(dāng)前幀等待超時(shí)，重發(fā)當(dāng)前幀有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSM

37、n一個(gè)有限狀態(tài)機(jī)由哪些元素組成？一個(gè)有限狀態(tài)機(jī)由哪些元素組成？n狀態(tài)、事件、動(dòng)作狀態(tài)、事件、動(dòng)作n轉(zhuǎn)移（變遷）轉(zhuǎn)移（變遷）n狀態(tài)狀態(tài)n狀態(tài)機(jī)有有限個(gè)狀態(tài)狀態(tài)機(jī)有有限個(gè)狀態(tài)（指穩(wěn)定狀態(tài)）（指穩(wěn)定狀態(tài)）n每一時(shí)刻只能處于一個(gè)特定狀態(tài)中，并等待某個(gè)事件的發(fā)生每一時(shí)刻只能處于一個(gè)特定狀態(tài)中，并等待某個(gè)事件的發(fā)生n事件事件n如收到如收到PDU，時(shí)間超時(shí)等都為事件，時(shí)間超時(shí)等都為事件n事件可能會(huì)引起實(shí)體動(dòng)作事件可能會(huì)引起實(shí)體動(dòng)作n事件是狀態(tài)轉(zhuǎn)移的必要條件事件是狀態(tài)轉(zhuǎn)移的必要條件n動(dòng)作動(dòng)作n處理隊(duì)列中的某個(gè)事件，轉(zhuǎn)移到一個(gè)狀態(tài)處理隊(duì)列中的某個(gè)事件，轉(zhuǎn)移到一個(gè)狀態(tài)n不同狀態(tài)下，對(duì)同一事件處理可能不同不同狀態(tài)下

38、，對(duì)同一事件處理可能不同n可能忽略事件，保持原狀態(tài)可能忽略事件，保持原狀態(tài)FSM事件事件狀態(tài)狀態(tài)State 1State 2狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移事件事件2/動(dòng)作動(dòng)作2事件事件3/動(dòng)作動(dòng)作3事件事件1/動(dòng)作動(dòng)作1有限狀態(tài)機(jī)有限狀態(tài)機(jī)FSMn以停等協(xié)議為例，說(shuō)明：以停等協(xié)議為例，說(shuō)明：n狀態(tài)機(jī)的位置在哪里？狀態(tài)機(jī)的位置在哪里？n狀態(tài)如何確定？（難點(diǎn)）狀態(tài)如何確定？（難點(diǎn)）n發(fā)送方狀態(tài)機(jī)發(fā)送方狀態(tài)機(jī)n接收方狀態(tài)機(jī)接收方狀態(tài)機(jī)n協(xié)議系統(tǒng)狀態(tài)機(jī)協(xié)議系統(tǒng)狀態(tài)機(jī)n考慮發(fā)送、接收和信道情況考慮發(fā)送、接收和信道情況停等協(xié)議狀態(tài)機(jī)的位置停等協(xié)議狀態(tài)機(jī)的位置獲取獲取SDU狀態(tài)機(jī)狀態(tài)機(jī)遞交遞交SDU發(fā)送發(fā)送PDU、ACK

39、接收接收PDU、ACK去對(duì)等去對(duì)等實(shí)體實(shí)體對(duì)等實(shí)對(duì)等實(shí)體來(lái)體來(lái)協(xié)議實(shí)體協(xié)議實(shí)體停等協(xié)議狀態(tài)機(jī)的狀態(tài)停等協(xié)議狀態(tài)機(jī)的狀態(tài)n發(fā)送方：兩個(gè)狀態(tài)：發(fā)送方：兩個(gè)狀態(tài)：準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀0 、準(zhǔn)備發(fā)送幀、準(zhǔn)備發(fā)送幀1n接收方：兩個(gè)狀態(tài)：接收方：兩個(gè)狀態(tài)：等待幀等待幀0 、等待幀、等待幀1ACK(1)PDU（1）ACK(0)DATAPDU（0）PDU（0）DATAACK(1)DATADATADATADATA準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀1準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀0等待幀等待幀1等待幀等待幀0n狀態(tài)是復(fù)合的，可能由狀態(tài)是復(fù)合的，可能由多個(gè)要素組成：多個(gè)要素組成：如：接收方等待幀如：接收方等待幀1 l剛收到幀剛收到幀0 ，

40、正確，正確l已上交數(shù)據(jù)已上交數(shù)據(jù)l已發(fā)送已發(fā)送ACK發(fā)送方發(fā)送方接收方接收方停等協(xié)議發(fā)送方狀態(tài)機(jī)停等協(xié)議發(fā)送方狀態(tài)機(jī)準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀1準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀0收到收到ACK（1）發(fā)送幀發(fā)送幀1超時(shí)超時(shí)重發(fā)幀重發(fā)幀0超時(shí)超時(shí)重發(fā)幀重發(fā)幀1收到收到ACK（0）發(fā)送幀發(fā)送幀0收到收到NAK（0）重發(fā)幀重發(fā)幀0收到收到NAK（1）重發(fā)幀重發(fā)幀1注意：注意：ACK（1）：表示接收方已收到幀）：表示接收方已收到幀0，希望下一幀收幀，希望下一幀收幀1此處此處NAK（0）和和ACK（0），），對(duì)發(fā)方含義一樣對(duì)發(fā)方含義一樣停等協(xié)議接收方狀態(tài)機(jī)停等協(xié)議接收方狀態(tài)機(jī)等待幀等待幀0等待幀等待幀1收到幀收到幀0發(fā)發(fā)A

41、CK（1）超時(shí)超時(shí)發(fā)發(fā)ACK （0）或不發(fā)送但或不發(fā)送但重置重置T收到幀收到幀1發(fā)發(fā)ACK（0）收到錯(cuò)幀收到錯(cuò)幀NAK（0）/或不發(fā)送或不發(fā)送收到錯(cuò)幀收到錯(cuò)幀NAK（1）/或不發(fā)送或不發(fā)送超時(shí)超時(shí)發(fā)發(fā)ACK （1）或不發(fā)送但或不發(fā)送但重置重置T停等協(xié)議狀態(tài)機(jī)的狀態(tài)（另一種理解）停等協(xié)議狀態(tài)機(jī)的狀態(tài)（另一種理解）準(zhǔn)備發(fā)送準(zhǔn)備發(fā)送等待應(yīng)答等待應(yīng)答SDU已從上層來(lái)已從上層來(lái)發(fā)送幀發(fā)送幀seq=（s=Ns）Ns+超時(shí)超時(shí)重發(fā)幀重發(fā)幀收到收到ACK（s+1）收到收到NAK（s）重發(fā)幀重發(fā)幀Ns為為發(fā)送的發(fā)送的PDU序號(hào)序號(hào)發(fā)送方發(fā)送方等待接收等待接收PDU（S=Nr），期望的），期望的PDU上交上交SD

42、U，Nr+,發(fā)發(fā)ACK錯(cuò)或非期望的錯(cuò)或非期望的PDUNAK（Nr）超時(shí)超時(shí)ACK（Nr）Nr為期望接收的為期望接收的PDU序號(hào)序號(hào)接收方接收方事件產(chǎn)生，并沒(méi)事件產(chǎn)生，并沒(méi)有動(dòng)作，但發(fā)生有動(dòng)作，但發(fā)生了狀態(tài)轉(zhuǎn)移了狀態(tài)轉(zhuǎn)移進(jìn)一步理解有限狀態(tài)機(jī)進(jìn)一步理解有限狀態(tài)機(jī)n同一種協(xié)議的狀態(tài)機(jī)可能不是唯一的同一種協(xié)議的狀態(tài)機(jī)可能不是唯一的n不同的理解和出發(fā)點(diǎn)考慮不同的理解和出發(fā)點(diǎn)考慮n只要是穩(wěn)定的狀態(tài)并能描述協(xié)議即可只要是穩(wěn)定的狀態(tài)并能描述協(xié)議即可n事件是狀態(tài)轉(zhuǎn)移的必要條件事件是狀態(tài)轉(zhuǎn)移的必要條件n事件產(chǎn)生動(dòng)作事件產(chǎn)生動(dòng)作n可能產(chǎn)生狀態(tài)轉(zhuǎn)移可能產(chǎn)生狀態(tài)轉(zhuǎn)移n也可能不產(chǎn)生狀態(tài)轉(zhuǎn)移也可能不產(chǎn)生狀態(tài)轉(zhuǎn)移n事件有時(shí)不

43、產(chǎn)生動(dòng)作，也可產(chǎn)生狀態(tài)轉(zhuǎn)移事件有時(shí)不產(chǎn)生動(dòng)作，也可產(chǎn)生狀態(tài)轉(zhuǎn)移n動(dòng)作一定需要事件來(lái)觸發(fā)，沒(méi)有事件的動(dòng)作所產(chǎn)生的動(dòng)作一定需要事件來(lái)觸發(fā)，沒(méi)有事件的動(dòng)作所產(chǎn)生的狀態(tài)是不穩(wěn)定的狀態(tài)是不穩(wěn)定的State 1狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移事件事件1/動(dòng)作動(dòng)作1事件事件1/或或事件事件2/動(dòng)作動(dòng)作2或或 事件事件2/State 1狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移/動(dòng)作動(dòng)作1根據(jù)有限狀態(tài)機(jī)形成狀態(tài)轉(zhuǎn)移表根據(jù)有限狀態(tài)機(jī)形成狀態(tài)轉(zhuǎn)移表 狀態(tài)狀態(tài) 事件事件動(dòng)作動(dòng)作事件事件1事件事件2事件事件2事件事件n狀態(tài)狀態(tài)1處理處理下一狀態(tài)下一狀態(tài)狀態(tài)狀態(tài)2處理處理下一狀態(tài)下一狀態(tài)狀態(tài)狀態(tài)n處理處理下一狀態(tài)下一狀態(tài)停等協(xié)議發(fā)送狀態(tài)轉(zhuǎn)移表停等協(xié)議發(fā)送狀態(tài)轉(zhuǎn)

44、移表準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀1準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀0收到收到ACK（1）發(fā)送幀發(fā)送幀1超時(shí)超時(shí)重發(fā)幀重發(fā)幀0超時(shí)超時(shí)重發(fā)幀重發(fā)幀1收到收到ACK（0）發(fā)送幀發(fā)送幀0收到收到NAK（0）重發(fā)幀重發(fā)幀0收到收到NAK（1）重發(fā)幀重發(fā)幀1 狀態(tài)狀態(tài) 事件事件動(dòng)作動(dòng)作收到收到ACK（1）或）或 NAK（1）超時(shí)超時(shí)收到收到ACK（0）或或 NAK（0）準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀1處理處理發(fā)送幀發(fā)送幀1重發(fā)幀重發(fā)幀0重發(fā)幀重發(fā)幀0下一狀態(tài)下一狀態(tài)準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀0/準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀0處理處理重發(fā)幀重發(fā)幀1重發(fā)幀重發(fā)幀1發(fā)送幀發(fā)送幀0下一狀態(tài)下一狀態(tài)/準(zhǔn)備發(fā)送幀準(zhǔn)備發(fā)送幀1fsm程序框架程序框架n根據(jù)狀態(tài)轉(zhuǎn)

45、移表形成根據(jù)狀態(tài)轉(zhuǎn)移表形成fsm程序可能的框架程序可能的框架fsm( 當(dāng)前狀態(tài)當(dāng)前狀態(tài),事件事件 ）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（當(dāng)前狀態(tài)（當(dāng)前狀態(tài)=X）用用FSM方式編程的網(wǎng)絡(luò)仿真軟件方式編程的網(wǎng)絡(luò)仿真軟件Optimized Network Engineering T

46、ools (OPNET) A three layer modeling hierarchy Network ModelNode Model用用FSM方式編程的網(wǎng)絡(luò)仿真軟件方式編程的網(wǎng)絡(luò)仿真軟件Node ModelP r o c e s s ModelProcess Model有限狀態(tài)機(jī)對(duì)協(xié)議的驗(yàn)證有限狀態(tài)機(jī)對(duì)協(xié)議的驗(yàn)證n對(duì)協(xié)議可靠性的驗(yàn)證對(duì)協(xié)議可靠性的驗(yàn)證n協(xié)議是否有死鎖協(xié)議是否有死鎖n協(xié)議是否有不正確的狀態(tài)轉(zhuǎn)換協(xié)議是否有不正確的狀態(tài)轉(zhuǎn)換n對(duì)可達(dá)性的驗(yàn)證對(duì)可達(dá)性的驗(yàn)證n是否有不可達(dá)的狀態(tài)（無(wú)效狀態(tài)）是否有不可達(dá)的狀態(tài)（無(wú)效狀態(tài)）n是否有效狀態(tài)都可達(dá)是否有效狀態(tài)都可達(dá)n驗(yàn)證協(xié)議需要從系統(tǒng)的角度去考慮驗(yàn)證協(xié)議需要從系統(tǒng)的角度去考慮n發(fā)送方、接收方、信道發(fā)送方、接收方、信道有限狀態(tài)機(jī)對(duì)協(xié)議的驗(yàn)證有限狀態(tài)機(jī)對(duì)協(xié)議的驗(yàn)證n以停等協(xié)議為例討論以停等協(xié)議為例討論n如何從系統(tǒng)的角度考慮變量和狀態(tài)如何從系統(tǒng)的角度考慮變量和狀態(tài)n如何確定有效狀態(tài)如何確定有效狀態(tài)n驗(yàn)證可達(dá)性驗(yàn)證可達(dá)性n如何驗(yàn)證協(xié)議死鎖如何驗(yàn)證協(xié)議死鎖n如何驗(yàn)證協(xié)議失敗如何驗(yàn)證協(xié)議失敗停等協(xié)議的變量與狀態(tài)停等協(xié)議的變量與狀態(tài)n變量變量（3個(gè)變量個(gè)變量XYZ）n發(fā)送方變量發(fā)送方變量Xn接收方變量接收方變量Yn信道變量（半雙工）信道變量（半雙工）Zn狀態(tài)狀態(tài)n所有變量的各種組合所有變量的各種組合n任何時(shí)刻