計(jì)算機(jī)網(wǎng)絡(luò) 8

1、停止等待協(xié)議的工作原理 時(shí) 間 AB DATA0 送 主 機(jī) ACK DATA1 送 主 機(jī) ACK (a) 正常情況 AB DATA0 DATA0 送 主 機(jī) ACK (c) 數(shù)據(jù)幀丟失 重 傳 tout 丟 失 ！ AB DATA0 送 主 機(jī) ACK DATA0 丟 棄 ACK (d) 確認(rèn)幀丟失 重 傳 tout丟 失 ！ 三種情況 3.3.2 停止等待協(xié)議的算法 按照習(xí)慣的表示法，ACKn 表示“第 n 1 號(hào)幀 已經(jīng)收到，現(xiàn)在期望接收第 n 號(hào)幀”。 nACK1 表示“0 號(hào)幀已收到，現(xiàn)在期望接收的下一 幀是 1 號(hào)幀”； nACK0 表示“1 號(hào)幀已收到，現(xiàn)在期望接收的下一 幀是

2、 0 號(hào)幀”。 停止等待協(xié)議的工作原理 時(shí) 間 AB DATA0 送 主 機(jī) ACK DATA1 送 主 機(jī) ACK (a) 正常情況 AB DATA0 DATA0 送 主 機(jī) ACK (c) 數(shù)據(jù)幀丟失 重 傳 tout 丟 失 ！ AB DATA0 送 主 機(jī) ACK DATA0 丟 棄 ACK (d) 確認(rèn)幀丟失 重 傳 tout丟 失 ！ 三種情況 3.3.3 停止等待協(xié)議的重傳時(shí)間 n設(shè) tf 是一個(gè)數(shù)據(jù)幀的發(fā)送時(shí)間，且數(shù)據(jù)幀的長(zhǎng)度是固 定不變的。顯然，數(shù)據(jù)幀的發(fā)送時(shí)間 tf 是數(shù)據(jù)幀的長(zhǎng) 度 lf (bit)與數(shù)據(jù)的發(fā)送速率 C (bit/s)之比，即 tf = lf /C = l

3、f /C (s) （3-1） n發(fā)送時(shí)間 tf 也就是數(shù)據(jù)幀的發(fā)送時(shí)延。 n數(shù)據(jù)幀沿鏈路傳到結(jié)點(diǎn)B還要經(jīng)歷一個(gè)傳播時(shí)延 tp。 n結(jié)點(diǎn) B 收到數(shù)據(jù)幀要花費(fèi)時(shí)間進(jìn)行處理，此時(shí)間稱為 處理時(shí)間 tpr，發(fā)送確認(rèn)幀 ACK 的發(fā)送時(shí)間為 ta。 停止等待協(xié)議中數(shù)據(jù)幀和確認(rèn)幀 的發(fā)送時(shí)間關(guān)系 AB DATA DATA ACK 傳播時(shí)延 tp 處理時(shí)間 tpr 確認(rèn)幀發(fā)送時(shí)間 ta 傳播時(shí)延 tp 處理時(shí)間 tpr tT 時(shí)間 兩個(gè)成功發(fā)送的 數(shù)據(jù)幀之間的 最小時(shí)間間隔 數(shù)據(jù)幀的 發(fā)送時(shí)間 tf 設(shè)置的 重傳時(shí)間 tout 重傳時(shí)間 n重傳時(shí)間選為略大于“從發(fā)完數(shù)據(jù)幀到收到確認(rèn)幀所 需的平均時(shí)間”。

4、n為方便起見，我們?cè)O(shè)重傳時(shí)間為 tout = tp + tpr+ ta + tp + tpr (3-2) 簡(jiǎn)單的數(shù)學(xué)分析 n兩個(gè)發(fā)送成功的數(shù)據(jù)幀之間的最小時(shí)間間隔是 tT n設(shè)數(shù)據(jù)幀出現(xiàn)差錯(cuò)(包括幀丟失)的概率為 p， 但假設(shè)確認(rèn)幀不會(huì)出現(xiàn)差錯(cuò)。 n設(shè)正確傳送一個(gè)數(shù)據(jù)幀所需的平均時(shí)間 tav tav = tT ( 1 + 一個(gè)幀的平均重傳次數(shù)) 簡(jiǎn)單的數(shù)學(xué)分析（續(xù)） 一幀的平均重傳次數(shù) = 1 P重傳次數(shù)為 1 + 2 P重傳次數(shù)為 2 + 3 P重傳次數(shù)為 3 + = 1 P第 1 次發(fā)送出錯(cuò) P第 2 次發(fā)送成功 + 2 P第 1, 2 次發(fā)送出錯(cuò) P第 3 次發(fā)送成功 + 3 P第 1,

5、 2, 3 次發(fā)送出錯(cuò) P第 4 次發(fā)送成功 + = p(1 p) + 2p2(1 p) + 3p3(1 p) + 這里 PX 是出現(xiàn)事件 X 的概率。 另一種分析方法 n正確傳送一個(gè)數(shù)據(jù)幀所需的平均時(shí)間 tav ntav =Et=tT*(i+1)*P重傳次數(shù)為 i (i=0) ntav= tT (i+1)*(1-p)pi ntav= tT (1-p) pi+tT (1-p) i*pi ntav= tT1+(1-p) i*pi (i=1) 簡(jiǎn)單的數(shù)學(xué)分析（續(xù)） 得出正確傳送一個(gè)數(shù)據(jù)幀所需的平均時(shí)間： 當(dāng)傳輸差錯(cuò)率增大時(shí)，tav 也隨之增大。當(dāng)無(wú)差錯(cuò)時(shí)，p = 0, tav = tT。 )1 (

6、 /)1 ( 1 pttipptt i TT i Tav (3-5) 簡(jiǎn)單的數(shù)學(xué)分析（續(xù)） 每秒成功發(fā)送的平均幀數(shù)就是鏈路的平均吞吐量 av。顯然， av = 1/tav = (1 p) / tT (3-6) 最大吞吐量應(yīng)為： max = 1/tT 停止等待協(xié)議 ARQ 的優(yōu)缺點(diǎn) n優(yōu)點(diǎn)：比較簡(jiǎn)單 。 n缺點(diǎn)：通信信道的利用率不高，也就是說(shuō)，信 道還遠(yuǎn)遠(yuǎn)沒(méi)有被數(shù)據(jù)比特填滿。尤其當(dāng)信道好 時(shí)，這么做很浪費(fèi)時(shí)間。 n為了克服這一缺點(diǎn)，就產(chǎn)生了另外兩種協(xié)議， 即連續(xù) ARQ 和選擇重傳 ARQ。這將在后面進(jìn) 一步討論。 3.4發(fā)送窗口大于1的 ARQ 協(xié)議 3.4.1 連續(xù) ARQ 協(xié)議的工作原理

7、n在發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來(lái)等待確認(rèn) 幀，而是可以連續(xù)再發(fā)送若干個(gè)數(shù)據(jù)幀。 n如果這時(shí)收到了接收端發(fā)來(lái)的確認(rèn)幀，那么還 可以接著發(fā)送數(shù)據(jù)幀。 n由于減少了等待時(shí)間，整個(gè)通信的吞吐量就提 高了。 連續(xù) ARQ 協(xié)議的工作原理 DATA0 DATA1 DATA2 DATA3 DATA4 DATA5 重傳 DATA2 重傳 DATA3 ACK1 ACK2 ACK1 確認(rèn) DATA0 ACK2 確認(rèn) DATA1 DATA2 出錯(cuò)，丟棄 DATA3 不按序，丟棄，重傳 ACK2 DATA4 不按序，丟棄，重傳 ACK2 DATA5 不按序，丟棄，重傳 ACK2 ACK3 ACK3 確認(rèn) DATA2

8、 ACK4 確認(rèn) DATA3 ACK4 重傳 DATA5 重傳 DATA4 超 時(shí) 重 傳 時(shí) 間 AB tout 送交主機(jī) 送交主機(jī) ? ACK2 ACK2 ACK2 需要注意： (1) 接收端只按序接收數(shù)據(jù)幀。雖然在有差錯(cuò)的 2號(hào)幀之 后接著又收到了正確的 3 個(gè)數(shù)據(jù)幀，但接收端都必須 將這些幀丟棄，因?yàn)樵谶@些幀前面有一個(gè) 2 號(hào)幀還沒(méi) 有收到。雖然丟棄了這些不按序的無(wú)差錯(cuò)幀，但應(yīng)重 復(fù)發(fā)送已發(fā)送過(guò)的最后一個(gè)確認(rèn)幀（防止確認(rèn)幀丟 失）。 (2) ACK1 表示確認(rèn) 0 號(hào)幀 DATA0，并期望下次收到 1 號(hào) 幀；ACK2 表示確認(rèn) 1 號(hào)幀 DATA1，并期望下次收到 2 號(hào)幀。依此類推

9、。 需要注意： (3) 結(jié)點(diǎn) A 在每發(fā)送完一個(gè)數(shù)據(jù)幀時(shí)都要設(shè)置該幀的超時(shí) 計(jì)時(shí)器。如果在所設(shè)置的超時(shí)時(shí)間內(nèi)收到確認(rèn)幀，就 立即將超時(shí)計(jì)時(shí)器清零。但若在所設(shè)置的超時(shí)時(shí)間到 了而未收到確認(rèn)幀，就要重傳相應(yīng)的數(shù)據(jù)幀（仍需重 新設(shè)置超時(shí)計(jì)時(shí)器）。 在等不到 2 號(hào)幀的確認(rèn)而重傳 2 號(hào)數(shù)據(jù)幀時(shí)，雖 然結(jié)點(diǎn) A 已經(jīng)發(fā)完了 5 號(hào)幀，但A仍必須向回走，將 2號(hào)幀及其以后的各幀全部進(jìn)行重傳。連續(xù) ARQ 又稱 為Go-back-N ARQ，意思是當(dāng)出現(xiàn)差錯(cuò)必須重傳時(shí)， 要向回走 N 個(gè)幀，然后再開始重傳。 需要注意： (4) 以上講述的僅僅是連續(xù) ARQ 協(xié)議的工作原理。協(xié)議 在具體實(shí)現(xiàn)時(shí)還有許多的細(xì)節(jié)

10、。 3.3.3 滑動(dòng)窗口的概念 n滑動(dòng)窗口的作用: n(1) 當(dāng)未被確認(rèn)的數(shù)據(jù)幀太多時(shí)，只要有一幀出錯(cuò)，就可能 要有很多的數(shù)據(jù)幀需要重傳，浪費(fèi)很多時(shí)間。 n(2) 為了對(duì)所發(fā)送出去的大量數(shù)據(jù)幀編號(hào)，每個(gè)數(shù)據(jù)幀的發(fā) 送序號(hào)也要占用大量開銷。 n發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口 。 n發(fā)送窗口用來(lái)對(duì)發(fā)送端進(jìn)行流量控制。 n發(fā)送窗口的大小 WT 代表在還沒(méi)有收到對(duì)方確認(rèn)信息的情 況下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。 01234567012 發(fā)送窗口 WT 不允許發(fā)送這些幀允許發(fā)送 5 個(gè)幀 (a) 01234567012 不允許發(fā)送這些幀還允許發(fā)送 4 個(gè)幀 WT 已發(fā)送 (b) 01234

11、567012 不允許發(fā)送這些幀 WT 已發(fā)送 (c) 01234567012 不允許發(fā)送這些幀 還允許發(fā)送 3 個(gè)幀 WT 已發(fā)送 已發(fā)送 并已收到確認(rèn) (d) 接收端設(shè)置接收窗口 n在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收 窗口內(nèi)才允許將該數(shù)據(jù)幀收下。 n若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其 丟棄。 n在連續(xù) ARQ 協(xié)議中，接收窗口的大小 WR = 1。 n只有當(dāng)收到的幀的序號(hào)與接收窗口一致時(shí)才能接收該幀。 否則，就丟棄它。 n每收到一個(gè)序號(hào)正確的幀，接收窗口就向前（即向右方） 滑動(dòng)一個(gè)幀的位置。同時(shí)發(fā)送對(duì)該幀的確認(rèn)。 不允許接收這些幀 01234567012 WR 準(zhǔn)備接收

12、0 號(hào)幀 (a) 不允許接收這些幀 01234567012 WR 準(zhǔn)備接收 1 號(hào)幀 已收到 (b) 不允許接收這些幀 01234567012 WR 準(zhǔn)備接收 4 號(hào)幀 已收到 (c) 滑動(dòng)窗口的重要特性 n只有在接收窗口向前滑動(dòng)時(shí)（與此同時(shí) 也發(fā)送了確認(rèn)），發(fā)送窗口才有可能向 前滑動(dòng)。 n收發(fā)兩端的窗口按照以上規(guī)律不斷地向 前滑動(dòng)，因此這種協(xié)議又稱為滑動(dòng)窗口 協(xié)議。 n當(dāng)發(fā)送窗口和接收窗口的大小都等于 1 時(shí)，就是停止等待協(xié)議。 問(wèn) 題 n當(dāng)采用 3 bit 編碼時(shí)，發(fā)送窗口的設(shè)成9 行不行？ n當(dāng)采用 3 bit 編碼時(shí)，發(fā)送窗口的設(shè)成8 行不行？ 發(fā)送窗口的最大值 n當(dāng)用 n 個(gè)比特進(jìn)行

13、編號(hào)時(shí)，若接收窗口 的大小為 1，則只有在發(fā)送窗口的大小 WT 2n 1時(shí)，連續(xù) ARQ 協(xié)議才能正確 運(yùn)行。 n例如，當(dāng)采用 3 bit 編碼時(shí)，發(fā)送窗口的 最大值是 7 而不是 8。 n設(shè)成9肯定不行。 3.3.4 信道利用率 n由于每個(gè)數(shù)據(jù)幀都必須包括一定的控制 信息(如幀的序號(hào)、地址、同步信息以及 其他的一些控制信息)，所以即使連續(xù)不 停地發(fā)送數(shù)據(jù)幀，信道利用率(即扣除全 部的控制信息后的數(shù)據(jù)率與信道容量之 比)也不可能達(dá)到 100 %。 n當(dāng)出現(xiàn)差錯(cuò)時(shí)(這是不可避免的)，數(shù)據(jù)幀 的不斷重傳將進(jìn)一步使信道利用率降低。 n書上信道利用率的公式不做介紹。 最佳幀長(zhǎng) n若數(shù)據(jù)幀的幀長(zhǎng)取得很短，那么控制信 息在每一幀中所占的比例就增大，因而 額外開銷增大，這就導(dǎo)致信道利用率的 下降。 n若幀長(zhǎng)取得太長(zhǎng)，則數(shù)據(jù)幀在傳輸過(guò)程 中出錯(cuò)的概率就增大，于是重傳次數(shù)將 增大，這也會(huì)使信道利用率下降。 n由此可見，存在一個(gè)最佳幀長(zhǎng)，在此幀 長(zhǎng)下信道