講海明碼滑動窗口機制

第8講海明碼和流量控制協(xié)議海明碼流量控制

非受限協(xié)議

停-等協(xié)議退后N幀協(xié)議選擇性重傳協(xié)議海明碼碼字（codeword）：一個幀包括m個數(shù)據(jù)位，r個校驗位，n=m+r，則此n比特單元稱為n位碼字海明距離（Hammingdistance）：兩個碼字之間不同的比特位數(shù)目例：與的海明距離為5編碼系統(tǒng)中，任意兩個碼字的最小碼距就是該編碼系統(tǒng)的碼距

海明碼信息序號a0a1a200001001201030114100510161107111信息序號a0a1a2a30000011001210103001141100501016011071111系統(tǒng)碼距為1系統(tǒng)碼距為2海明碼為使系統(tǒng)檢測一位錯誤，碼距最小為2為使系統(tǒng)糾正一位錯誤，碼距最小為3海明碼系統(tǒng)中，有關(guān)系式：L－1＝C＋DL：碼距

D：檢錯位數(shù)

C：糾錯位數(shù)

D≥C碼距檢錯糾錯100210311421522632733海明碼海明距離與糾錯性能如果兩個碼字的海明距離為d，則需要d個單比特錯就可以把一個碼字轉(zhuǎn)換成另一個碼字為了檢查d個錯，需要使用海明距離為d+1的編碼為了糾正d個錯，需要使用海明距離為

2d+1的編碼海明碼設(shè)計糾錯碼要求：糾正單比特錯(m個信息位，r個校驗位)對2m個合法碼字中任何一個，有n個與其距離為1的非法碼字，因此有：(n+1)2m

2n

利用n=m+r，得到(m+r+1)2r給定m，利用該式可以得出校正單比特誤碼的校驗位數(shù)目的下界海明碼有效信息位數(shù)m與校驗位數(shù)r的關(guān)系海明碼基本思想將r位校驗位分成r組，采用奇偶校驗的方式產(chǎn)生r位檢錯信息，這些檢錯信息能指示出傳輸信息中哪一位發(fā)生了錯誤有效信息位數(shù)m校驗位數(shù)r1~435~11412~26527~57658~1207海明碼的生成確定所需最少的校驗位數(shù)碼位從右邊/左邊開始編號，從“1”開始位號為2的冪的位是校驗位，編號為r1,r2…r2n-1;其余位是信息位，編號為d1,d2…dn每個校驗位使得包括自己在內(nèi)的一些位的“1”的個數(shù)為奇數(shù)/偶數(shù)（奇偶校驗）為看清信息位k對哪些校驗位有影響，將k寫成2的冪的和例：11=1+2+8海明碼海明碼例：對7位信息1001000進(jìn)行偶校驗海明編碼。

7位信息需要4位校驗，編號為r1,r2,r4,r8B1B2B3B4

B5B6B7B8

B9B10B11

海明碼：

r1

r2

d1

r4

d2

d3

d4r8

d5d6d7

00

110010000r1=d1+d2+d4+d5+d7r2=d1+d3+d4+d6+d7r4=d2+d3+d4r8=d5+d6+d7s1=r1+d1+d2+d4+d5+d7s2=r2+d1+d3+d4+d6+d7s3=r4+d2+d3+d4s4=r8+d5+d6+d712

345678

91011111112222244488

8海明監(jiān)督關(guān)系式海明碼工作過程1每個碼字到來后，接收方計算海明監(jiān)督關(guān)系式是否全部等于0，如果是，則證明接收數(shù)據(jù)無誤；否，則證明數(shù)據(jù)出錯出錯的位數(shù)可以根據(jù)海明監(jiān)督關(guān)系式推出，由sn…s2s1組成的值等于出錯的位數(shù)海明碼海明碼工作過程2每個碼字到來前，接收方計數(shù)器清零接收方檢查每個校驗位k(k=1,2,4…)的奇偶值是否正確若第k位奇偶值不對，計數(shù)器加k所有校驗位檢查完后，若計數(shù)器值為0，則碼字有效；若計數(shù)器值為m，則第m位出錯若校驗位1、2、8出錯，則第11位變反海明碼海明碼例.接收碼字為：0011101(7/4碼，從左至右編碼)，求：信息碼解：1)由海明碼的監(jiān)督關(guān)系式計算得S3S2S1=1012)由監(jiān)督關(guān)系式推出：出錯位是第5位

3)對第5位取反，得正確碼字：0011

0

014)把第1、2、4位的冗余碼刪除，得發(fā)送端的信息碼：1001海明碼使用海明碼糾正突發(fā)錯誤可采用k個碼字（n=m+r）組成

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

kn矩陣kr個校驗位，km個數(shù)據(jù)位，可糾正最多為k個的突發(fā)性連續(xù)比特錯12

345678

91011111112222244488

82流量控制

數(shù)據(jù)鏈路層上控制的是網(wǎng)絡(luò)中相鄰結(jié)點之間的數(shù)據(jù)傳輸局域網(wǎng)廣域網(wǎng)主機

H1主機

H2路由器

R1路由器

R2路由器

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

H1

向

H2

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

H1主機

H2路由器

R1路由器

R2路由器

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

H1

向

H2

發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動數(shù)據(jù)鏈路層的簡單模型完全理想化的數(shù)據(jù)傳輸

所基于的兩個假定假定1：鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。假定2：不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交主機。既不需要差錯控制，也不需要流量控制2.1非受限協(xié)議（烏托邦）數(shù)據(jù)只作單向傳輸傳送和接收雙方的網(wǎng)絡(luò)一直處于就緒狀態(tài)處理時間不計，緩沖空間無限大在數(shù)據(jù)鏈路層之間的交互信道從不損壞或丟失發(fā)送方不停發(fā)送，接收方不停接收2.2停—等協(xié)議去掉第二個假定，即不能保證接收方向主機交付數(shù)據(jù)的速率永遠(yuǎn)不低于發(fā)送方發(fā)送數(shù)據(jù)的速率。但保留第一個假定，即發(fā)送方與接收方之間傳輸數(shù)據(jù)的信道仍然是無差錯的理想信道。發(fā)送方發(fā)送一個幀后，不繼續(xù)發(fā)送幀而是等待接收方發(fā)來一個確認(rèn)。這種協(xié)議稱為停-等協(xié)議。由接收方控制發(fā)送方的數(shù)據(jù)發(fā)送速率，是計算機網(wǎng)絡(luò)中流量控制的一個基本方法。2.2?！葏f(xié)議協(xié)議算法在發(fā)送結(jié)點：

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

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

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

(4)等待。

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

(1)等待。

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

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

(4)向發(fā)送結(jié)點發(fā)確認(rèn)信息，表示數(shù)據(jù)幀已上交主機。

(5)轉(zhuǎn)到(1)。兩種情況的對比（傳輸均無差錯）ABDATADATADATADATA送主機B送主機B送主機B送主機BABDATA送主機BDATA送主機B時間非受限協(xié)議不需要流量控制停-等協(xié)議需要流量控制實用的停止等待協(xié)議（有可能產(chǎn)生差錯）時間ABDATA0送主機ACKDATA1送主機ACK(a)正常情況ABDATA0DATA0送主機ACK(c)數(shù)據(jù)幀丟失重傳tout丟失！ABDATA0送主機ACKDATA0丟棄ACK(d)確認(rèn)幀丟失重傳tout丟失！ABDATA0NAKDATA0送主機ACK(b)數(shù)據(jù)幀出錯重傳出錯四種情況引入了兩個概念：1、tout2、幀編號

超時計時器的作用結(jié)點A發(fā)送完一個數(shù)據(jù)幀時，就啟動一個超時計時器(timeouttimer)。若到了超時計時器所設(shè)置的重傳時間tout而仍收不到結(jié)點B的任何確認(rèn)幀，則結(jié)點A就重傳前面所發(fā)送的這一數(shù)據(jù)幀。一般可將重傳時間選為略大于“從發(fā)完數(shù)據(jù)幀到收到確認(rèn)幀所需的平均時間”。解決重復(fù)幀的問題使每一個數(shù)據(jù)幀帶上不同的發(fā)送序號。每發(fā)送一個新的數(shù)據(jù)幀就把它的發(fā)送序號加1。若結(jié)點B收到發(fā)送序號相同的數(shù)據(jù)幀，就表明出現(xiàn)了重復(fù)幀。這時應(yīng)丟棄重復(fù)幀，因為已經(jīng)收到過同樣的數(shù)據(jù)幀并且也交給了主機B。但此時結(jié)點B還必須向A發(fā)送確認(rèn)幀ACK，因為B已經(jīng)知道A還沒有收到上一次發(fā)過去的確認(rèn)幀ACK。幀的編號問題如何對幀進(jìn)行編號？任何一個編號系統(tǒng)的序號所占用的比特數(shù)一定是有限的。因此，經(jīng)過一段時間后，發(fā)送序號就會重復(fù)。序號占用的比特數(shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷就越小。對于停止等待協(xié)議，由于每發(fā)送一個數(shù)據(jù)幀就停止等待，因此用一個比特來編號就夠了。一個比特可表示0和1兩種不同的序號。

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

tout=tp+tpr+ta+tp+tpr

設(shè)上式右端的處理時間tpr

和確認(rèn)幀的發(fā)送時間ta

都遠(yuǎn)小于傳播時延tp，因此可將重傳時間取為兩倍的傳播時延，即tout=2tp停止等待協(xié)議ARQ的優(yōu)缺點優(yōu)點：比較簡單。缺點：通信信道的利用率不高，也就是說，信道還遠(yuǎn)遠(yuǎn)沒有被數(shù)據(jù)比特填滿。為了克服這一缺點，提出了捎帶確認(rèn)技術(shù)，和滑動窗口協(xié)議。捎帶確認(rèn)機制捎帶確認(rèn)技術(shù)(piggybacking)

為提高信道利用率，考慮使用同一線路來傳輸兩個方向的數(shù)據(jù)：A到B的確認(rèn)幀可以與A到B的數(shù)據(jù)幀合并一起發(fā)送，這種將確認(rèn)幀暫時延遲，以便與下一個數(shù)據(jù)幀共同發(fā)送的技術(shù)被稱為捎帶確認(rèn)捎帶確認(rèn)帶來的新問題

為了捎帶一個確認(rèn)，應(yīng)該等待多長的時間2.3滑動窗口協(xié)議每個數(shù)據(jù)幀攜帶一個序列號，范圍從0~2n-1滑動窗口協(xié)議的本質(zhì)是：發(fā)送方總是維持著一個發(fā)送窗口，窗口內(nèi)的序列號對應(yīng)著那些允許發(fā)送以及已經(jīng)被發(fā)送但還未收到確認(rèn)的幀。發(fā)送窗口用來對發(fā)送端進(jìn)行流量控制。接收方總是維持著一個接收窗口，窗口內(nèi)的序列號對應(yīng)著它可以接收的幀，任何落在窗口之外的幀都將被丟棄發(fā)送方的窗口與接收方的窗口不必有同樣的上下界，也不一定是同樣的大小01234567012發(fā)送窗口WT不允許發(fā)送這些幀允許發(fā)送5個幀(a)01234567012不允許發(fā)送這些幀還允許發(fā)送4個幀WT已發(fā)送(b)01234567012不允許發(fā)送這些幀WT已發(fā)送(c)01234567012不允許發(fā)送這些幀還允許發(fā)送

3個幀WT已發(fā)送

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

1號幀已收到(b)不允許接收這些幀01234567012WR準(zhǔn)備接收4號幀已收到(c)滑動窗口的重要特性只有在接收窗口向前滑動時（與此同時也發(fā)送了確認(rèn)），發(fā)送窗口才有可能向前滑動。收發(fā)兩端的窗口按照以上規(guī)律不斷地向前滑動，因此這種協(xié)議又稱為滑動窗口協(xié)議。當(dāng)發(fā)送窗口和接收窗口的大小都等于1時，就是停止等待協(xié)議。2.3.1一位滑動窗口協(xié)議1位滑動窗口協(xié)議

發(fā)送方在發(fā)送一個數(shù)據(jù)幀之后，必須要等待相關(guān)的確認(rèn)才可以發(fā)送下一幀，所以它是一個采取了捎帶確認(rèn)技術(shù)的停－等協(xié)議2.3.1一位滑動窗口協(xié)議大小為1、采用3位序列號的滑動窗口的數(shù)據(jù)傳輸?shù)倪^程(a)初始時(b)第一個幀發(fā)出之后(c)第一個幀接收之后(d)第一個確認(rèn)收到之后一位滑動窗口協(xié)議的兩種情形(雙方同時發(fā)送分組)數(shù)據(jù)包格式：seq，ack，packetnumber(a)正常情況（先后發(fā)送）(b)不正常情況（同時發(fā)送）默認(rèn)的假設(shè)：一個幀到達(dá)接收方所需要的傳輸時間可以忽略不計，這樣的假設(shè)是明顯不合理的例：數(shù)據(jù)發(fā)送速率為50kbps的衛(wèi)星信道，它的往返傳播延遲為500ms，若采用停－等協(xié)議發(fā)送1000b的幀，信道利用率是多少？t=20ms時，數(shù)據(jù)被完全發(fā)送出去t=270ms時，數(shù)據(jù)到達(dá)接收方t=520ms時，確認(rèn)回到接收方(假設(shè)接收方處理速度很快，確認(rèn)幀很短)這意味著，500/520＝96％的時間發(fā)送方是被阻塞的，只有4％的有效帶寬在被使用1位滑動窗口協(xié)議的信道利用率若信道容量為b位/秒，幀長為1位，往返傳輸時間為R秒，則信道利用率為1/(1+bR)為提高信道利用率，采用管道化技術(shù)（pipelining）在發(fā)送完一個數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個數(shù)據(jù)幀如果這時收到了接收端發(fā)來的確認(rèn)幀，那么可以接著發(fā)送數(shù)據(jù)幀1位滑動窗口協(xié)議的信道利用率2.3.2退后N幀協(xié)議拋棄一種技巧性的假設(shè)一個幀到達(dá)接收方的傳輸時間，加上確認(rèn)幀來回的傳輸時間是可以忽略不計。解決策略允許發(fā)送過程在阻塞之前發(fā)送多達(dá)w個幀，而不是1幀。由于可以適當(dāng)?shù)倪x擇w，發(fā)送過程就可以在等待往返傳輸?shù)臅r間內(nèi)連續(xù)傳輸幀，而不至于填滿窗口。退后N幀的工作原理

在發(fā)送完一個數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個數(shù)據(jù)幀。如果這時收到了接收端發(fā)來的確認(rèn)幀，那么還可以接著發(fā)送數(shù)據(jù)幀。由于減少了等待時間，整個通信的吞吐量就提高了。要求接收方的數(shù)據(jù)鏈路層必須按次序把分組交給網(wǎng)絡(luò)層。當(dāng)幀n的確認(rèn)到達(dá)時，幀n-1,n-2等也都被自動確認(rèn)。接收窗口>1滑動窗口示意圖退后N幀協(xié)議的思路接收方將出錯的幀及其后續(xù)幀一起丟棄，對出錯的幀不發(fā)送確認(rèn)幀；發(fā)送方在出錯幀的確認(rèn)幀超時后，從出錯的