【文章內(nèi)容簡介】 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ī) 網(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ī) 網(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ī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 循環(huán)冗余檢驗 循環(huán)冗余校驗 CRC (Cyclic Redundancy Check) :數(shù)據(jù)通信中應(yīng)用最廣的一種檢驗差錯方法。方法是在發(fā)送端用數(shù)學(xué)方法產(chǎn)生一個循環(huán)碼，叫做循環(huán)冗余檢驗碼。在信息碼位之后隨信息一起發(fā)出。在接收端也用同樣方法產(chǎn)生一個循環(huán)冗余校驗碼。將這兩個校驗碼進(jìn)行比較，如果一致就證明所傳信息無誤；如果不一致就表明傳輸中有差錯，并要求發(fā)送端再傳輸 .進(jìn)一步詳細(xì)說明如下 : 計 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 無論傳輸系統(tǒng)的設(shè)計再怎么完美 ,差錯總會存在 ,它可能導(dǎo)致傳輸?shù)膸杏幸粋€或多個比特被改變。這就需要差錯檢測，差錯檢測的執(zhí)行要依靠計算差錯檢測碼，它是傳輸比特的一個函數(shù)。差錯檢測碼附加在傳輸比特的后面。接收器會根據(jù)收到的比特來計算差錯檢測碼，然后與收到的差錯檢測碼相比較，并根據(jù)比較結(jié)果判斷傳輸過程中是否出現(xiàn)差錯。循環(huán)冗余檢驗（ Cyclical Redundancy Check，簡稱 CRC）是一種最常用也最有效的差錯檢測碼，描述如下。給定一個 k比特的比特塊，或者說報文，發(fā)送器會生成一個（ nk）比特的比特序列，稱為幀檢驗序列（ FCS），這個比特序列要使最后得到的含有 n比特的幀可以被一些預(yù)先設(shè)定的數(shù)值整除。然后，接收器用同樣的數(shù)值對接收到的幀進(jìn)行除法運(yùn)算，如其結(jié)果沒有余數(shù)，則認(rèn)為沒有差錯。 計 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 計 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 上例中發(fā)送的數(shù)據(jù)是 :101000110101110,后面加的就是 FCS,接收端收到這樣數(shù)據(jù)后 ,除以同樣的生成函數(shù)的系數(shù) ,余數(shù)若為零 ,表示數(shù)據(jù)傳輸正確 . 上面的生成多項式為 x5+x4+x2+1. 按照生成多項式的采用 ,可以分為標(biāo)準(zhǔn) CRC和非標(biāo)準(zhǔn) CRC,前者采用 CRC4,CRC16,CRC32,CRC32C,CRCCCITT等多項式生成 ,后者由用戶由于特殊通信目的采用 . 例 :要發(fā)送 101,P(x)=x4+x3+X2+1,余數(shù)為 :0011,所以發(fā)送的數(shù)據(jù)為 1010011,該結(jié)果為確認(rèn)和重傳的依據(jù) .請大家驗證接收方的余數(shù)是否為零 . 計 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 停止等待協(xié)議的算法 在發(fā)送結(jié)點 ： （ 1） 從主機(jī)取一個數(shù)據(jù)幀 。 （ 2） V(S)← 0。 {發(fā)送狀態(tài)變量初始化 } （ 3） N(S)←V(S) ； {將發(fā)送狀態(tài)變量的數(shù)值寫入發(fā)送序號 } 將數(shù)據(jù)幀送交發(fā)送緩存 。 （ 4） 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去 。 （ 5） 設(shè)置超時計時器 。 {選擇適當(dāng)?shù)某瑫r重傳時間 tout } 計 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 （ 6）等待。 {等待以下 3個事件中最先出現(xiàn)的一個 } （ 7）若收到確認(rèn)幀 ACK，則： 從主機(jī)取一個新的數(shù)據(jù)幀； V(S)←[1 ? V(S)]； {更新發(fā)送狀態(tài)變量，變?yōu)橄乱粋€序號 } 轉(zhuǎn)到 (3)。 （ 8）若收到否認(rèn)幀 NAK，則轉(zhuǎn)到 (4)。 {重傳數(shù)據(jù)幀 } （ 9）若超時計時器時間到，則轉(zhuǎn)到 (4)。 {重傳數(shù)據(jù)幀 } 計 算 機(jī) 網(wǎng) 絡(luò) 教 程 第 4 章 數(shù) 據(jù) 鏈 路 層 在接收結(jié)點 ： （ 1） V(R)←0 。 {接收狀態(tài)變量初始化，其數(shù)值等于欲接收的數(shù)據(jù)幀的發(fā)送序號 } （ 2）等待。 （ 3）當(dāng)收到一個數(shù)據(jù)幀，就檢查有無產(chǎn)生傳