【文章內(nèi)容簡(jiǎn)介】 first time from a retransmission ? Use a sequence number in the header of each frame. What is the minimum number of bits needed for the sequence number ? A 1bit sequence number (0 or 1) suffices here. 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 /*Protocol 3 (par) */ define MAX_SEQ 1 /* must be 1 for protocol 3 */ typedef enum {frame_arrival, cksum_err, timeout} event_type。 include void sender3(void) { seq_nr next_frame_to_send。 /* seq number of next outgoing frame */ frame s。 /* buffer for an outbound frame */ packet buffer。 /* buffer for an outbound packet */ event_type event。 /* frame_arrival is the only possiblity */ next_frame_to_send = 0。 /* initialize outbound sequence numbers */ from_work_layer(amp。buffer)。 /* fetch first packet */ while (true) { = buffer。 /* construct a frame for transmission */ = next_frame_to_send。 /* insert sequence number in frame */ to_physical_layer(amp。s)。 /* send it on its way */ start_timer()。 /* if answer takes too long, time out */ wait_for_event(amp。event)。 /* frame_arrival, cksum_err, timeout */ if(event == frame_arrival) { from_work_layer(amp。buffer)。/* get the next one to send */ inc(next_frame_to_send)。 /* invert next_frame_to_send */ } } } 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 void receiver3(void) { seq_nr frame_expected。 frame r, s。 /* buffers for frames */ event_type event。 /* filled in by wait, but not used here */ frame_expected = 0。 while(true) { wait_for_event(amp。event)。 /* frame_arrival, cksum_err */ if(event == frame_arrival) { /* a valid frame has arrived */ from_physical_layer(amp。r)。 /* go get the inbound frame */ if( == frame_expected){ to_work_layer(amp。)。/*pass the data to the work layer*/ inc(frame_expected)。 /* next time expect the other seq nr */ } to_physical_layer(amp。s)。 /* none of the fields are used */ } } } 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 循環(huán)冗余檢驗(yàn) 循環(huán)冗余校驗(yàn) CRC (Cyclic Redundancy Check) :數(shù)據(jù)通信中應(yīng)用最廣的一種檢驗(yàn)差錯(cuò)方法。方法是在發(fā)送端用數(shù)學(xué)方法產(chǎn)生一個(gè)循環(huán)碼，叫做循環(huán)冗余檢驗(yàn)碼。在信息碼位之后隨信息一起發(fā)出。在接收端也用同樣方法產(chǎn)生一個(gè)循環(huán)冗余校驗(yàn)碼。將這兩個(gè)校驗(yàn)碼進(jìn)行比較，如果一致就證明所傳信息無(wú)誤；如果不一致就表明傳輸中有差錯(cuò)，并要求發(fā)送端再傳輸 .進(jìn)一步詳細(xì)說明如下 : 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 無(wú)論傳輸系統(tǒng)的設(shè)計(jì)再怎么完美 ,差錯(cuò)總會(huì)存在 ,它可能導(dǎo)致傳輸?shù)膸杏幸粋€(gè)或多個(gè)比特被改變。這就需要差錯(cuò)檢測(cè)，差錯(cuò)檢測(cè)的執(zhí)行要依靠計(jì)算差錯(cuò)檢測(cè)碼，它是傳輸比特的一個(gè)函數(shù)。差錯(cuò)檢測(cè)碼附加在傳輸比特的后面。接收器會(huì)根據(jù)收到的比特來計(jì)算差錯(cuò)檢測(cè)碼，然后與收到的差錯(cuò)檢測(cè)碼相比較，并根據(jù)比較結(jié)果判斷傳輸過程中是否出現(xiàn)差錯(cuò)。循環(huán)冗余檢驗(yàn)（ Cyclical Redundancy Check，簡(jiǎn)稱 CRC）是一種最常用也最有效的差錯(cuò)檢測(cè)碼，描述如下。給定一個(gè) k比特的比特塊，或者說報(bào)文，發(fā)送器會(huì)生成一個(gè)（ nk）比特的比特序列，稱為幀檢驗(yàn)序列（ FCS），這個(gè)比特序列要使最后得到的含有 n比特的幀可以被一些預(yù)先設(shè)定的數(shù)值整除。然后，接收器用同樣的數(shù)值對(duì)接收到的幀進(jìn)行除法運(yùn)算，如其結(jié)果沒有余數(shù)，則認(rèn)為沒有差錯(cuò)。 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 上例中發(fā)送的數(shù)據(jù)是 :101000110101110,后面加的就是 FCS,接收端收到這樣數(shù)據(jù)后 ,除以同樣的生成函數(shù)的系數(shù) ,余數(shù)若為零 ,表示數(shù)據(jù)傳輸正確 . 上面的生成多項(xiàng)式為 x5+x4+x2+1. 按照生成多項(xiàng)式的采用 ,可以分為標(biāo)準(zhǔn) CRC和非標(biāo)準(zhǔn) CRC,前者采用 CRC4,CRC16,CRC32,CRC32C,CRCCCITT等多項(xiàng)式生成 ,后者由用戶由于特殊通信目的采用 . 例 :要發(fā)送 101,P(x)=x4+x3+X2+1,余數(shù)為 :0011,所以發(fā)送的數(shù)據(jù)為 1010011,該結(jié)果為確認(rèn)和重傳的依據(jù) .請(qǐng)大家驗(yàn)證接收方的余數(shù)是否為零 . 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 停止等待協(xié)議的算法 在發(fā)送結(jié)點(diǎn) ： （ 1） 從主機(jī)取一個(gè)數(shù)據(jù)幀 。 （ 2） V(S)← 0。 {發(fā)送狀態(tài)變量初始化 } （ 3） N(S)←V(S) ； {將發(fā)送狀態(tài)變量的數(shù)值寫入發(fā)送序號(hào) } 將數(shù)據(jù)幀送交發(fā)送緩存 。 （ 4） 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去 。 （ 5） 設(shè)置超時(shí)計(jì)時(shí)器 。 {選擇適當(dāng)?shù)某瑫r(shí)重傳時(shí)間 tout } 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 （ 6）等待。 {等待以下 3個(gè)事件中最先出現(xiàn)的一個(gè) } （ 7）若收到確認(rèn)幀 ACK，則： 從主機(jī)取一個(gè)新的數(shù)據(jù)幀； V(S)←[1 ? V(S)]； {更新發(fā)送狀態(tài)變量，變?yōu)橄乱粋€(gè)序號(hào) } 轉(zhuǎn)到 (3)。 （ 8）若收到否認(rèn)幀 NAK，則轉(zhuǎn)到 (4)。 {重傳數(shù)據(jù)幀 } （ 9）若超時(shí)計(jì)時(shí)器時(shí)間到，則轉(zhuǎn)到 (4)。 {重傳數(shù)據(jù)幀 } 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 在接收結(jié)點(diǎn) ： （ 1） V(R)←0 。 {接收狀態(tài)變量初始化，其數(shù)值等于欲接收的數(shù)據(jù)幀的發(fā)送序號(hào) } （ 2）等待。 （ 3）當(dāng)收到一個(gè)數(shù)據(jù)幀，就檢查有無(wú)產(chǎn)生傳