第8講 海明碼和滑動窗口機制

流量控制

非受限協(xié)議

停-等協(xié)議第8講海明碼和停等協(xié)議1碼字（codeword）：一個幀包括m個數(shù)據(jù)位，r個校驗位，n=m+r，則此n比特單元稱為n位碼字。海明距離（Hammingdistance）：兩個碼字之間不同的比特位數(shù)目。例：0000000000與0000011111的海明距離為51海明碼*2如果兩個碼字的海明距離為d，則需要d個單比特錯就可以把一個碼字轉(zhuǎn)換成另一個碼字；為了檢查出d個錯（單比特錯），需要使用海明距離為d+1的編碼；為了糾正d個錯，需要使用海明距離為2d+1的編碼；1海明碼31海明碼設(shè)計糾錯碼要求：m個信息位，r個校驗位，糾正單比特錯；對2m個有效信息中任何一個，有n個與其距離為1的無效碼字，因此有：(n+1)2m

2n

利用n=m+r，得到(m+r+1)2r

給定m，利用該式可以得出校正單比特誤碼的校驗位數(shù)目的下界41海明碼碼位從右邊開始編號，從“1”開始；位號為2的冪的位是校驗位，其余是信息位；每個校驗位使得包括自己在內(nèi)的一些位的奇偶值為偶數(shù)（或奇數(shù)）。為看清數(shù)據(jù)位k對哪些校驗位有影響，將k寫成2的冪的和。例：11=1+2+851海明碼工作過程每個碼字到來前，接收方計數(shù)器清零；接收方檢查每個校驗位k(k=1,2,4…)的奇偶值是否正確；若第k位奇偶值不對，計數(shù)器加k；所有校驗位檢查完后，若計數(shù)器值為0，則碼字有效；若計數(shù)器值為m，則第m位出錯。若校驗位1、2、8出錯，則第11位變反。6使用海明碼糾正突發(fā)錯誤可采用k個碼字（n=m+r）組成

kn矩陣，按列發(fā)送，接收方恢復成

kn矩陣kr個校驗位，km個數(shù)據(jù)位，可糾正最多為k個的突發(fā)性連續(xù)比特錯。1海明碼7數(shù)據(jù)：1011010d7d6d5d4d3d2d1

位置：111098

765

4321海明碼：10101010000 d7d6d5

r8

d4d3d2

r4d1

r2

r11海明碼8

111098

7654321

海明碼：10101010000

d7d6d5

r8

d4d3d2

r4d1

r2r1

接收方接收到數(shù)據(jù)后，按照同樣的規(guī)則進行奇偶校驗得出新的r1，r2，r4，r8。如果傳輸正確，對于偶校驗來說，這4個新值都應為0。假設(shè)第4位發(fā)生了錯誤，即接收到的數(shù)據(jù)為1000，那么接收方計算的結(jié)果是：r1=0，r2=0，r4=1，r8=0，4位組合起來為0100，即表示第4位出現(xiàn)了錯誤，然后把1取反，從而糾正了該錯誤。

1海明碼912345678

91011111112222244488

8102流量控制數(shù)據(jù)鏈路層上控制的是網(wǎng)絡(luò)中相鄰結(jié)點之間的數(shù)據(jù)傳輸網(wǎng)絡(luò)層控制的是網(wǎng)絡(luò)源結(jié)點和目的結(jié)點之間的數(shù)據(jù)傳輸傳輸層控制的是網(wǎng)絡(luò)中不同結(jié)點內(nèi)發(fā)送進程和接收進程之間的數(shù)據(jù)傳輸。11數(shù)據(jù)只作單向傳輸傳送和接收雙方的網(wǎng)絡(luò)一直處于就緒狀態(tài)處理時間不計，緩沖空間無限大在數(shù)據(jù)鏈路層之間的交互信道從不損壞或丟失2.1非受限協(xié)議（烏托邦）12完全理想化的數(shù)據(jù)傳輸

所基于的兩個假定假定1：鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。假定2：不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交主機。這個假定就相當于認為：接收端向主機交付數(shù)據(jù)的速率永遠不會低于發(fā)送端發(fā)送數(shù)據(jù)的速率。13局域網(wǎng)廣域網(wǎng)主機

H1主機

H2路由器

R1路由器

R2路由器

R3電話網(wǎng)局域網(wǎng)主機

H1

向

H2

發(fā)送數(shù)據(jù)鏈路層應用層運輸層網(wǎng)絡(luò)層物理層鏈路層應用層運輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從層次上來看數(shù)據(jù)的流動數(shù)據(jù)鏈路層的簡單模型14局域網(wǎng)廣域網(wǎng)主機

H1主機

H2路由器

R1路由器

R2路由器

R3電話網(wǎng)局域網(wǎng)主機

H1

向

H2

發(fā)送數(shù)據(jù)鏈路層應用層運輸層網(wǎng)絡(luò)層物理層鏈路層應用層運輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動數(shù)據(jù)鏈路層的簡單模型15現(xiàn)在去掉上述的第二個假定。但是，仍然保留第一個假定，即主機A向主機B傳輸數(shù)據(jù)的信道仍然是無差錯的理想信道。然而現(xiàn)在不能保證接收端向主機交付數(shù)據(jù)的速率永遠不低于發(fā)送端發(fā)送數(shù)據(jù)的速率。由收方控制發(fā)方的數(shù)據(jù)流，乃是計算機網(wǎng)絡(luò)中流量控制的一個基本方法。2.2?！葏f(xié)議162.2?！葏f(xié)議17在發(fā)送結(jié)點：

(1)從主機取一個數(shù)據(jù)幀。

(2)將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。

(3)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。

(4)等待。

(5)若收到由接收結(jié)點發(fā)過來的信息(此信息的格式與內(nèi)容可由雙方事先商定好)，則從主機取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)。協(xié)議算法18在接收結(jié)點：

(1)等待。

(2)若收到由發(fā)送結(jié)點發(fā)過來的數(shù)據(jù)幀，則將其放入數(shù)據(jù)鏈路層的接收緩存。

(3)將接收緩存中的數(shù)據(jù)幀上交主機。

(4)向發(fā)送結(jié)點發(fā)一信息，表示數(shù)據(jù)幀已經(jīng)上交給主機。

(5)轉(zhuǎn)到(1)。協(xié)議算法19兩種情況的對比（傳輸均無差錯）ABDATADATADATADATA送主機B送主機B送主機B送主機BABDATA送主機BDATA送主機B時間不需要流量控制需要流量控制20實用的停止等待協(xié)議時間ABDATA0送主機ACKDATA1送主機ACK(a)正常情況ABDATA0DATA0送主機ACK(c)數(shù)據(jù)幀丟失重傳tout丟失！ABDATA0送主機ACKDATA0丟棄ACK(d)確認幀丟失重傳tout丟失！ABDATA0NAKDATA0送主機ACK(b)數(shù)據(jù)幀出錯重傳出錯四種情況212.2?！葏f(xié)議22超時計時器的作用結(jié)點A發(fā)送完一個數(shù)據(jù)幀時，就啟動一個超時計時器(timeouttimer)。若到了超時計時器所設(shè)置的重傳時間tout而仍收不到結(jié)點B的任何確認幀，則結(jié)點A就重傳前面所發(fā)送的這一數(shù)據(jù)幀。一般可將重傳時間選為略大于“從發(fā)完數(shù)據(jù)幀到收到確認幀所需的平均時間”。23解決重復幀的問題使每一個數(shù)據(jù)幀帶上不同的發(fā)送序號。每發(fā)送一個新的數(shù)據(jù)幀就把它的發(fā)送序號加1。若結(jié)點B收到發(fā)送序號相同的數(shù)據(jù)幀，就表明出現(xiàn)了重復幀。這時應丟棄重復幀，因為已經(jīng)收到過同樣的數(shù)據(jù)幀并且也交給了主機B。但此時結(jié)點B還必須向A發(fā)送確認幀ACK，因為B已經(jīng)知道A還沒有收到上一次發(fā)過去的確認幀ACK。24幀的編號問題任何一個編號系統(tǒng)的序號所占用的比特數(shù)一定是有限的。因此，經(jīng)過一段時間后，發(fā)送序號就會重復。序號占用的比特數(shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷就越小。對于停止等待協(xié)議，由于每發(fā)送一個數(shù)據(jù)幀就停止等待，因此用一個比特來編號就夠了。一個比特可表示0和1兩種不同的序號。

25幀的發(fā)送序號數(shù)據(jù)幀中的發(fā)送序號N(S)以0和1交替的方式出現(xiàn)在數(shù)據(jù)幀中。每發(fā)一個新的數(shù)據(jù)幀，發(fā)送序號就和上次發(fā)送的不一樣。用這樣的方法就可以使收方能夠區(qū)分開新的數(shù)據(jù)幀和重傳的數(shù)據(jù)幀了。26停止等待協(xié)議的要點連續(xù)出現(xiàn)相同發(fā)送序號的數(shù)據(jù)幀，表明發(fā)送端進行了超時重傳。連續(xù)出現(xiàn)相同序號的確認幀，表明接收端收到了重復幀。發(fā)送端在發(fā)送完數(shù)據(jù)幀時，必須在其發(fā)送緩存中暫時保留這個數(shù)據(jù)幀的副本。這樣才能在出差錯時進行重傳。只有確認對方已經(jīng)收到這個數(shù)據(jù)幀時，才可以清除這個副本。27停止等待協(xié)議的要點發(fā)送端對出錯的數(shù)據(jù)幀進行重傳是自動進行的，因而這種差錯控制體制常簡稱為ARQ(AutomaticRepeatreQuest)，直譯是自動重傳請求，但意思是自動請求重傳。28停等協(xié)議的效率分析29停止等待協(xié)議中數(shù)據(jù)幀和確認幀的發(fā)送時間關(guān)系A(chǔ)BDATADATAACK傳播時延tp處理時間tpr確認幀發(fā)送時間ta傳播時延tp處理時間tprtT時間兩個成功發(fā)送的數(shù)據(jù)幀之間的最小時間間隔數(shù)據(jù)幀的發(fā)送時間tf設(shè)置的重傳時間tout30重傳時間重傳時間的作用是：數(shù)據(jù)幀發(fā)送完畢后若經(jīng)過了這樣長的時間還沒有收到確認幀，就重傳這個數(shù)據(jù)幀。為方便起見，我們設(shè)重傳時間為

tout=tp+tp