計(jì)算機(jī)網(wǎng)絡(luò)7課件

1、計(jì)算機(jī)網(wǎng)絡(luò)7計(jì)算機(jī)網(wǎng)絡(luò)7冗余碼的計(jì)算 用二進(jìn)制的模 2 運(yùn)算進(jìn)行 2n 乘 M 的運(yùn)算，這相當(dāng)于在 M 后面添加 n 個(gè) 0。得到的 (k + n) bit 的數(shù)除以事先選定好的長(zhǎng)度為 (n + 1) bit 的數(shù) P，得出商是 Q 而余數(shù)是 R，余數(shù) R 比除數(shù) P 至少要少1 個(gè)比特。 冗余碼的計(jì)算 用二進(jìn)制的模 2 運(yùn)算進(jìn)行 2n 乘 M 的運(yùn)冗余碼的計(jì)算舉例 模二加減法不進(jìn)位：如1111+1010=01011010-1101=0111書p79，n=3，P=1101，數(shù)據(jù)為101001000。設(shè) n = 5, P = 110101，數(shù)據(jù)是1010001101冗余碼的計(jì)算舉例 模二加減法不

2、進(jìn)位：如 1101010110 Q 商 除數(shù) P 110101 101000110100000 2nM 被除數(shù) 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余數(shù)循環(huán)冗余檢驗(yàn)的原理說(shuō)明 1101循環(huán)冗余檢驗(yàn)的舉例模 2 運(yùn)算的結(jié)果是：商 Q =1101010110，余數(shù)R = 01110。將余數(shù) R 作為冗余碼添加在數(shù)據(jù) M 的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或 2nM + R。 P可以表示為多項(xiàng)式的形式，如P=1101其多項(xiàng)式為P(x)=X3

3、+X2+1問(wèn)：P=110101的多項(xiàng)式表示是什么？循環(huán)冗余檢驗(yàn)的舉例模 2 運(yùn)算的結(jié)果是：商 Q =11010檢測(cè)出差錯(cuò) 在接收端，把收到的幀除以相同的P，只要得出的余數(shù) R 不為 0，就表示檢測(cè)到了差錯(cuò)。但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。一旦檢測(cè)出差錯(cuò)，就丟棄這個(gè)出現(xiàn)差錯(cuò)的幀。只要經(jīng)過(guò)嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù) P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。 檢測(cè)出差錯(cuò) 在接收端，把收到的幀除以相同的P，只要得出的余數(shù)應(yīng)當(dāng)注意 僅用循環(huán)冗余檢驗(yàn) CRC 差錯(cuò)檢測(cè)技術(shù)只能做到無(wú)差錯(cuò)接受(accept)?！盁o(wú)差錯(cuò)接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們

4、都能以非常接近于 1 的概率認(rèn)為這些幀在傳輸過(guò)程中沒(méi)有產(chǎn)生差錯(cuò)”。也就是說(shuō)：“凡是接受的幀都沒(méi)有傳輸差錯(cuò)”（有差錯(cuò)的幀就丟棄而不接受）。要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認(rèn)和重傳機(jī)制。 應(yīng)當(dāng)注意 僅用循環(huán)冗余檢驗(yàn) CRC 差錯(cuò)檢測(cè)技術(shù)只能做到無(wú)差問(wèn) 題為什么數(shù)據(jù)鏈路層對(duì)錯(cuò)誤幀只是丟棄，而不是要求重傳?問(wèn) 題為什么數(shù)據(jù)鏈路層對(duì)錯(cuò)誤幀只是丟棄，而不是要求重傳?3.3 停止等待協(xié)議停止等待協(xié)議是最簡(jiǎn)單的但也是最基本的數(shù)據(jù)鏈路層協(xié)議?，F(xiàn)在，數(shù)據(jù)鏈路層普遍采用比較簡(jiǎn)單的不可靠傳輸協(xié)議，而把可靠傳輸?shù)呢?zé)任讓運(yùn)輸層來(lái)完成。3.3 停止等待協(xié)議停止等待協(xié)議是最簡(jiǎn)單的但也是最基本的3.3.

5、1 停止等待協(xié)議的工作原理在發(fā)送端，每發(fā)送完一幀后就停止發(fā)送，等待著接收端的確認(rèn)。如果收到來(lái)自接收端的確認(rèn)幀，就繼續(xù)發(fā)送下一幀。在接收端，每收到一個(gè)無(wú)差錯(cuò)的幀，就把這個(gè)幀交付給它的上層軟件（網(wǎng)絡(luò)層），并向發(fā)送端發(fā)送確認(rèn)幀。接收端若收到有差錯(cuò)的幀，就靜悄悄地丟棄這個(gè)幀，其他什么也不做。3.3.1 停止等待協(xié)議的工作原理在發(fā)送端，每發(fā)送完一幀后幀的編號(hào)問(wèn)題 為了保證可靠交付，發(fā)送端必須對(duì)所發(fā)送的幀進(jìn)行編號(hào)。由于每一次只發(fā)送一幀，因此停止等待協(xié)議只需要一個(gè)比特進(jìn)行編號(hào)。編號(hào)只有兩個(gè)值：0和1。第一次發(fā)送0號(hào)幀，下一次就發(fā)送1號(hào)幀，依此類推。在發(fā)送確認(rèn)幀時(shí)也應(yīng)當(dāng)明確是確認(rèn)對(duì)方哪一個(gè)數(shù)據(jù)幀的序號(hào)。按習(xí)慣

6、記法，ACKn表示已經(jīng)正確收到了第n號(hào)幀的前一個(gè)幀，并期待收到下一個(gè)第n號(hào)幀。幀的編號(hào)問(wèn)題 為了保證可靠交付，發(fā)送端必須對(duì)所發(fā)送的幀進(jìn)行編幀的編號(hào)問(wèn)題（續(xù)）因此，ACK0代表已正確接收編號(hào)為1的幀，并期待收到下一個(gè)編號(hào)為0的幀。同理， ACK1代表已正確接收編號(hào)為0的幀，并期待收到下一個(gè)編號(hào)為1的幀。幀的編號(hào)問(wèn)題（續(xù)）因此，ACK0代表已正確接收編號(hào)為1的幀，停止等待協(xié)議的工作原理時(shí)間ABDATA0送主機(jī)ACKDATA1送主機(jī)ACK(a) 正常情況ABDATA0DATA0送主機(jī)ACK(c) 數(shù)據(jù)幀丟失重傳tout丟失 ！ABDATA0送主機(jī)ACKDATA0丟棄ACK(d) 確認(rèn)幀丟失重傳tou

7、t丟失 ！三種情況停止等待協(xié)議的工作原理時(shí)ABDATA0送ACKDATA1送A超時(shí)計(jì)時(shí)器的作用結(jié)點(diǎn)A發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動(dòng)一個(gè)超時(shí)計(jì)時(shí)器(timeout timer)。計(jì)時(shí)器又稱為定時(shí)器。若到了超時(shí)計(jì)時(shí)器所設(shè)置的重傳時(shí)間 tout而仍收不到結(jié)點(diǎn) B 的任何確認(rèn)幀，則結(jié)點(diǎn) A 就重傳前面所發(fā)送的這一數(shù)據(jù)幀。一般可將重傳時(shí)間選為略大于“從發(fā)完數(shù)據(jù)幀到收到確認(rèn)幀所需的平均時(shí)間”。 超時(shí)計(jì)時(shí)器的作用結(jié)點(diǎn)A發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)，就啟動(dòng)一個(gè)超時(shí)計(jì)時(shí)幾個(gè)問(wèn)題問(wèn)題1：采用停止等待協(xié)議除了能重傳出錯(cuò)幀外，他還有什么優(yōu)點(diǎn)？問(wèn)題2：將幀編號(hào)的好處是什么？他解決了什么問(wèn)題？幾個(gè)問(wèn)題問(wèn)題1：采用停止等待協(xié)議除了能重傳

8、出錯(cuò)幀外，他還有什問(wèn)題1的回答1. 他還能起到流量控制的作用。發(fā)送端發(fā)送的速率一定要是接收端來(lái)得及接收，否則數(shù)據(jù)就會(huì)丟失。而停止等待協(xié)議要求對(duì)方接收完數(shù)據(jù)后再發(fā)確認(rèn)信息，發(fā)送端接收到確認(rèn)信息后才發(fā)送下一幀，這樣接收端就不會(huì)來(lái)不及接收。2. 他還能解決同學(xué)提出的后發(fā)先到的問(wèn)題。問(wèn)題1的回答1. 他還能起到流量控制的作用。發(fā)送端發(fā)送的速率問(wèn)題2的回答如果是確認(rèn)幀丟失，發(fā)送端也會(huì)重傳這一幀。這就會(huì)出現(xiàn)重復(fù)幀的問(wèn)題 。若結(jié)點(diǎn) B 收到發(fā)送序號(hào)相同的數(shù)據(jù)幀，就表明出現(xiàn)了重復(fù)幀。這時(shí)應(yīng)丟棄重復(fù)幀，因?yàn)橐呀?jīng)收到過(guò)同樣序號(hào)的數(shù)據(jù)幀并且也交給了主機(jī) B。但此時(shí)結(jié)點(diǎn) B 還必須向 A 發(fā)送確認(rèn)幀 ACK，因?yàn)?B

9、 已經(jīng)知道 A 還沒(méi)有收到上一次發(fā)過(guò)去的確認(rèn)幀 ACK。問(wèn)題2的回答如果是確認(rèn)幀丟失，發(fā)送端也會(huì)重傳這一幀。這就會(huì)出3.3.2 停止等待協(xié)議的算法 按照習(xí)慣的表示法，ACKn 表示“第 n 1 號(hào)幀已經(jīng)收到，現(xiàn)在期望接收第 n 號(hào)幀”。ACK1 表示“0 號(hào)幀已收到，現(xiàn)在期望接收的下一幀是 1 號(hào)幀”；ACK0 表示“1 號(hào)幀已收到，現(xiàn)在期望接收的下一幀是 0 號(hào)幀”。 3.3.2 停止等待協(xié)議的算法 按照習(xí)慣的表示法，AC在發(fā)送結(jié)點(diǎn) (1) 從主機(jī)取一個(gè)數(shù)據(jù)幀，送交發(fā)送緩存。(2) V(S)0。 (3) N(S)V(S)。(4) 將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。 (5) 設(shè)置超時(shí)計(jì)時(shí)器。(6)

10、 等待。 等待以下(7)和(8)這兩個(gè)事件中最先出現(xiàn)的一個(gè)(7) 收到確認(rèn)幀 ACKn， 若 n = 1 V(s)，則： 從主機(jī)取一個(gè)新的數(shù)據(jù)幀，放入發(fā)送緩存； V(S)1 V(S)，轉(zhuǎn)到 (3)。 否則，丟棄這個(gè)確認(rèn)幀，轉(zhuǎn)到(6)。 (8) 若超時(shí)計(jì)時(shí)器時(shí)間到，則轉(zhuǎn)到(4)。在發(fā)送結(jié)點(diǎn) (1) 從主機(jī)取一個(gè)數(shù)據(jù)幀，送交發(fā)送緩存。在接收結(jié)點(diǎn) (1) V(R)0。(2) 等待。(3) 收到一個(gè)數(shù)據(jù)幀；（假設(shè)數(shù)據(jù)已通過(guò)硬件CRC檢驗(yàn)） 若 N(S) = V(R)，則執(zhí)行(4)； 否則丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到(6)。(4) 將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件 （也就是數(shù)據(jù)鏈路層模型中的主機(jī)）。(5

11、) V(R)1 V(R)。(6) nV(R)； 發(fā)送確認(rèn)幀 ACKn，轉(zhuǎn)到(2)。 在接收結(jié)點(diǎn) (1) V(R)0。停止等待協(xié)議的要點(diǎn)只有收到序號(hào)正確的確認(rèn)幀 ACKn 后，才更新發(fā)送狀態(tài)變量 V(S)一次，并發(fā)送新的數(shù)據(jù)幀(7)。 接收端接收到數(shù)據(jù)幀時(shí)，就要將發(fā)送序號(hào) N(S) 與本地的接收狀態(tài)變量 V(R) 相比較 (3)。若二者相等就表明是新的數(shù)據(jù)幀，就收下，并發(fā)送確認(rèn)。否則為重復(fù)幀，就必須丟棄。但這時(shí)仍須向發(fā)送端發(fā)送確認(rèn)幀 ACKn，而接收狀態(tài)變量 V(R) 和確認(rèn)序號(hào) n 都不變。 停止等待協(xié)議的要點(diǎn)只有收到序號(hào)正確的確認(rèn)幀 ACKn 后，才停止等待協(xié)議的要點(diǎn)（續(xù)）發(fā)送端在發(fā)送完數(shù)據(jù)

12、幀時(shí)，必須在其發(fā)送緩存中暫時(shí)保留這個(gè)數(shù)據(jù)幀的副本。這樣才能在出差錯(cuò)時(shí)進(jìn)行重傳。只有確認(rèn)對(duì)方已經(jīng)收到這個(gè)數(shù)據(jù)幀時(shí)，才可以清除這個(gè)副本。 停止等待協(xié)議的要點(diǎn)（續(xù)）發(fā)送端在發(fā)送完數(shù)據(jù)幀時(shí)，必須在其發(fā)送停止等待協(xié)議的要點(diǎn)（續(xù)）實(shí)用的 CRC 檢驗(yàn)器都是用硬件完成的。CRC 檢驗(yàn)器能夠自動(dòng)丟棄檢測(cè)到的出錯(cuò)幀。因此所謂的“丟棄出錯(cuò)幀”，對(duì)上層軟件或用戶來(lái)說(shuō)都是感覺(jué)不到的。發(fā)送端對(duì)出錯(cuò)的數(shù)據(jù)幀進(jìn)行重傳是自動(dòng)進(jìn)行的，因而這種差錯(cuò)控制體制常簡(jiǎn)稱為 ARQ (Automatic Repeat reQuest)，直譯是自動(dòng)重傳請(qǐng)求，但意思是自動(dòng)請(qǐng)求重傳。 停止等待協(xié)議的要點(diǎn)（續(xù)）實(shí)用的 CRC 檢驗(yàn)器都是用硬件完成3.3.3 停止等待協(xié)議的重傳時(shí)間設(shè) tf 是一個(gè)數(shù)據(jù)幀的發(fā)送時(shí)間，且數(shù)據(jù)幀的長(zhǎng)度是固定不變的。顯然，數(shù)據(jù)幀的發(fā)送時(shí)間 tf 是數(shù)據(jù)幀的長(zhǎng)度 lf (