課件1計算機網(wǎng)絡(luò)第11章

1、Chapter 11 Link-Level Flow and Error Control1第 11 章鏈路級流量及差錯控制Chapter 11 Link-Level Flow and Error Control2流量控制和差錯控制概述決定通信鏈路、網(wǎng)絡(luò)及互聯(lián)網(wǎng)性能的主要機制是流量控制和差錯控制擁塞控制的基礎(chǔ)是控制源端發(fā)送PDU的流量以及控制經(jīng)過中間系統(tǒng)的PDU的流量差錯控制技術(shù)與流量控制技術(shù)密切相關(guān)，其目的是將傳輸過程中丟失或出現(xiàn)擁塞時丟棄的PDU恢復(fù)過來可在好幾個協(xié)議層次上實施：鏈路級, 網(wǎng)絡(luò)級 (如X.25), 運輸級或某些應(yīng)用級協(xié)議建立流量/差錯控制的性能分析模型極其困難Chapter

2、11 Link-Level Flow and Error Control3流量控制和差錯控制概述(續(xù))最簡單的情況是鏈路控制協(xié)議：運行在由點到點鏈路連起來的兩個設(shè)備之間，只需要考慮兩臺設(shè)備之間固定的傳播時延、固定的數(shù)據(jù)率、差錯概率，也許還有通信量的統(tǒng)計特性在處理網(wǎng)絡(luò)或互聯(lián)網(wǎng)絡(luò)的流量及差錯控制問題時，解析分析要復(fù)雜得多，要考慮的因素包括可變傳播時延、可變數(shù)據(jù)率、進入網(wǎng)絡(luò)的其他通信量源產(chǎn)生的擁塞的影響、動態(tài)選路決策的影響、多種邏輯連接之間的相對優(yōu)先級以及其他因素Chapter 11 Link-Level Flow and Error Control4流量控制流量控制是一種使目的端實體可以調(diào)節(jié)源端實

3、體發(fā)出的PDU流量的機制，它限制數(shù)據(jù)發(fā)送的數(shù)量或速率目的端限制流量的目的：源端可能試圖以比目的端可以處理的速率更快的速率發(fā)送PDU目的端的高層協(xié)議用戶可能接受數(shù)據(jù)較慢(緩存被充滿)，因而目的端可能需要限制源端的流量目的端可能將到來的數(shù)據(jù)緩存起來然后重新在另一個I/O端口上發(fā)送出去，它可能需要限制入流量以便與出流量相匹配Chapter 11 Link-Level Flow and Error Control5多個協(xié)議層次上的流量控制流量控制可以在多個協(xié)議級上實施，如多條X.25 虛電路復(fù)用到一條LAPB的數(shù)據(jù)鏈路上在高級別的邏輯連接上，每條邏輯連接上流量控制的實施是獨立的，而所有高級連接上的通信

4、量總和又在低級別上受到進一步的流量控制Chapter 11 Link-Level Flow and Error Control6流量控制實施范圍使流量控制研究更復(fù)雜的是它可能用于不同的場合，流量控制的協(xié)議級別與流量控制的實施范圍之間存在一定的關(guān)系Chapter 11 Link-Level Flow and Error Control7流量控制實施范圍(續(xù))一跳的范圍在兩個直接連接的中間系統(tǒng)之間，流量控制可以在鏈路級實施如在兩個鄰近的分組交換結(jié)點之間使用LAPB，為了保證結(jié)點緩存不產(chǎn)生溢出，可以使用LAPB流量控制限制進入通信量的大小鏈路級流量控制也可以用在互聯(lián)網(wǎng)中直接相連的兩個路由器之間，路由

5、器可以使用HDLC之類的鏈路級協(xié)議限制進入數(shù)據(jù)報的數(shù)量以免緩存溢出Chapter 11 Link-Level Flow and Error Control8流量控制實施范圍(續(xù))網(wǎng)絡(luò)接口鏈路級協(xié)議也常用在端系統(tǒng)與一個網(wǎng)絡(luò)或互聯(lián)網(wǎng)之間的接口鏈路上如在X.25分組交換網(wǎng)絡(luò)中，LAPB使得網(wǎng)絡(luò)可以限制端系統(tǒng)進入網(wǎng)絡(luò)的分組流量流量控制也可以在穿過網(wǎng)絡(luò)接口的網(wǎng)絡(luò)協(xié)議層實施這種情況下，流量控制是針對各個邏輯連接分別實施的，如在X.25中，可在端系統(tǒng)與網(wǎng)絡(luò)之間對每個單獨的虛電路實施流量控制Chapter 11 Link-Level Flow and Error Control9流量控制實施范圍(續(xù))進網(wǎng)到出

6、網(wǎng)有些網(wǎng)絡(luò)有一種進網(wǎng)到出網(wǎng)結(jié)點之間的邏輯連接(如虛電路)上實施的流量控制其目的是調(diào)節(jié)輸入通信量以免在出網(wǎng)結(jié)點上緩存發(fā)生溢出這種機制的細(xì)節(jié)對端用戶是透明的，但可以影響網(wǎng)絡(luò)接口上的數(shù)據(jù)流Chapter 11 Link-Level Flow and Error Control10流量控制實施范圍(續(xù))端到端在端系統(tǒng)之間的邏輯連接上實施；其目的在于接收端系統(tǒng)調(diào)節(jié)入流量以避免緩存溢出并滿足應(yīng)用的要求，如TCP在端系統(tǒng)之間的各個TCP連接上提供這樣的端到端流量控制，又如X.25網(wǎng)中在虛電路的基礎(chǔ)上也可以實施端到端的流量控制也經(jīng)常用于數(shù)據(jù)鏈路層，如LAN上運行的邏輯鏈路控制(LLC)就是在端系統(tǒng)之間實施的C

7、hapter 11 Link-Level Flow and Error Control11差錯控制差錯控制技術(shù)的用途是將信源與目的地之間傳送的PDU的丟失或損壞恢復(fù)過來它包括基于FCS的差錯檢測以及PDU重傳差錯控制和流量控制通常在一個單一的機制中一起實現(xiàn)，這個機制調(diào)節(jié)PDU的流量并確定什么時候需要重傳一個或多個PDU同流量控制一樣，差錯控制也可以在多種協(xié)議級別上實現(xiàn)Chapter 11 Link-Level Flow and Error Control12鏈路控制機制在鏈路級有3種常用的流量及差錯控制技術(shù):停止等待(Stop-and-wait)退N步(Go-back-N)拒選(Selecti

8、ve-reject)后兩種是滑動窗技術(shù)的兩個特例Chapter 11 Link-Level Flow and Error Control13幾點假設(shè)假設(shè)兩個端系統(tǒng)是由一條直接鏈路連接的源系統(tǒng)將報文分解成一系列幀進行發(fā)送，因為接收端的緩存大小可能有限傳輸越長，出錯的可能性越大，而出錯會引起整個幀重傳，用較小的幀就可以更快地檢測出差錯，而需要重傳的數(shù)據(jù)量也較小在共享媒體上(如LAN)，通常不允許一個站占據(jù)媒體過長的時間，以免造成其他發(fā)送站很長的時延Chapter 11 Link-Level Flow and Error Control14停止等待一個源端實體發(fā)送一個幀目的端實體收到后就發(fā)回一個對收

9、到幀的確認(rèn)來表示它愿意接收另一幀源端在發(fā)送下一幀之前必須等待直到收到這一確認(rèn)目的端因此僅僅通過不發(fā)確認(rèn)就可以讓數(shù)據(jù)流停下來Chapter 11 Link-Level Flow and Error Control15停止等待(續(xù))考慮兩類差錯:到達(dá)目的端的幀損壞了 幀中包含F(xiàn)CS，接收端檢測到差錯就丟棄這一幀；源站設(shè)置一個定時器，發(fā)完一幀后就等待確認(rèn)，如果定時器超時了還沒有收到確認(rèn)，就將同一幀再發(fā)一次，需要保留幀的副本到達(dá)源端的確認(rèn)幀損壞了 源端超時重發(fā)，接收端收到同一幀的兩個副本；為了避免這個問題，數(shù)據(jù)幀用0和1交替標(biāo)記，而確認(rèn)幀分為ACK0和ACK1兩種：ACK0對收到編號為1的幀做出確認(rèn)，

10、表示接收端準(zhǔn)備接收編號為0的幀Chapter 11 Link-Level Flow and Error Control16停止等待ARQ自動重傳請求，在所有鏈路級流量及差錯控制技術(shù)中出現(xiàn)使用:差錯檢測定時器確認(rèn)重傳停止等待ARQChapter 11 Link-Level Flow and Error Control17Figure 11.3Chapter 11 Link-Level Flow and Error Control18停止等待的效率停止等待技術(shù)由于低效率很少得到實際應(yīng)用低效率的根源是在一個時刻只能有一個正在傳輸?shù)膸绻麄鞑r延相對于傳輸時間很長，那么線路在大部分時間都是空閑的Cha

11、pter 11 Link-Level Flow and Error Control19Figure 11.4Chapter 11 Link-Level Flow and Error Control20停止等待的效率(續(xù))這種情況下很明顯線路的利用率不高假定不發(fā)生差錯，A將能以1/Tframe的速率發(fā)送數(shù)據(jù)幀因為要等待確認(rèn)，所以最大速率就降為1/(Tframe+2*Tprop+Tack)如果Tprop 相對于Tframe大得多，則吞吐量會降低很多Chapter 11 Link-Level Flow and Error Control21滑動窗技術(shù)通過允許多個幀同時傳輸以提高傳輸效率目的站分配了可

12、容納n個幀的緩存空間，因此可以接受n個幀源站可以連續(xù)發(fā)送n個幀而不需要等待任何確認(rèn)為了記錄下來到底哪些幀已經(jīng)被確認(rèn)過了，每個幀都用一個序號做標(biāo)記目的站確認(rèn)一個幀的方式是發(fā)送一個包含它期望收到的下一幀的序號的確認(rèn)(隱含地宣布它準(zhǔn)備接收下面的從指定的號碼開始的n個幀)這種方案可以用來確認(rèn)多個幀(累積確認(rèn))Chapter 11 Link-Level Flow and Error Control22滑動窗技術(shù)(續(xù))源站維護著一張允許發(fā)送的序號表，目的站維護著一張允許接收的序號表，這種表可認(rèn)為是一個幀的窗口，故稱為滑動窗流量控制序號要占幀中的一個字段，故其大小是有限的，對k bit字段，序號從0編到2k

13、-1滑動窗的工作過程(圖11.5)對于一個給定的序號長度實際窗口大小不必等于其最大可能值例子：3 bit序號字段，7幀的最大窗口(圖11.6)Chapter 11 Link-Level Flow and Error Control23Figure 11.5Chapter 11 Link-Level Flow and Error Control24Figure 11.6Chapter 11 Link-Level Flow and Error Control25Go-back-N ARQ鏈路控制協(xié)議中用到兩種滑動窗技術(shù)：go-back-N ARQ和拒選ARQ，它們的差別在于處理差錯的方式不同；其中

14、最常用的是前者一個站點可能發(fā)送一系列的幀，如果沒有出差錯，目的端就用一個RR幀確認(rèn)來到的幀如果目的站收到一個出錯的幀，就對此幀發(fā)送一個否認(rèn)(REJ)，并將丟棄這一幀以及所有即將到來的幀，直到出錯的幀被正確收到為止因此，源站收到一個REJ報文后，必須重傳出錯幀以及在此期間已發(fā)出的后續(xù)各幀Chapter 11 Link-Level Flow and Error Control26Go-back-N ARQ規(guī)則站A向站B發(fā)送幀，假定B已經(jīng)成功收到幀(i-1)而A剛發(fā)送完幀i，則考慮下列意外事件：損壞的幀，則B丟棄該幀并且不采取其他行動一段時間內(nèi)，A隨后發(fā)送幀(i+1)，B收到失序的幀(i+1)并發(fā)送

15、一個REJ i，A必須重傳幀i及所有后續(xù)幀隨后一段時間A并沒有發(fā)出更多的幀，B什么也沒收到，它既不返回RR也不返回REJ。當(dāng)A的定時器超時時，它傳送一個RR幀，其中的P位置1(要求B必須確認(rèn))，B以RR i進行確認(rèn)，A收到這個RR后就重傳幀i；另外一種情況是當(dāng)A的定時器超時時它也可能會重傳幀iChapter 11 Link-Level Flow and Error Control27Go-back-N ARQ規(guī)則(續(xù))2. 損壞的RR，B收到幀并發(fā)送RR(i+1)，但這個RR幀在傳送過程中丟失了因為確認(rèn)是累積的，所以A可能會收到后續(xù)的一個幀的RR，這個RR幀在與幀i相關(guān)的定時器超時前就到達(dá)了如

16、果A的定時器超時了，它就象在1b中那樣發(fā)送一個RR命令，并設(shè)置P位定時器。如果B沒能對RR命令做出反應(yīng)，或它的響應(yīng)損壞了，那么A的P位定時器就會超時，P位定時器超時后可以重發(fā)RR命令，這個過程可試多次，超過最大嘗試次數(shù)后就啟動一個復(fù)位過程3. REJ的損壞，同1b情形Chapter 11 Link-Level Flow and Error Control28Figure 11.7Chapter 11 Link-Level Flow and Error Control29拒選ARQ在拒選ARQ中，需要重傳的只有那些收到否定應(yīng)答(用SREJ表示)或那些超時的幀拒選看起來要比go-back-N效率更

17、高，因為它減少了重傳的量但接收端必須維持一個足夠大的緩存以便存放SREJ發(fā)過之后收到的各幀，直到出錯的幀被重傳；而且必須具有將收到的重傳幀插入到正確位置的邏輯功能發(fā)送端也要求更復(fù)雜的邏輯功能以便能夠不按順序發(fā)送一個幀由于其復(fù)雜性，拒選遠(yuǎn)不如go-back-N用的廣泛Chapter 11 Link-Level Flow and Error Control30ARQ的性能下面討論點到點鏈路上使用ARQ技術(shù)的一些性能問題停止等待ARQ無差錯停止等待有差錯的停止等待ARQ定義一個重要參數(shù)a，它抓住了數(shù)據(jù)鏈路性能特征的本質(zhì)，使用它可以簡化對go-back-N和拒選性能的討論滑動窗ARQ：無差錯滑動窗流量

18、控制、拒選ARQ和go-back-N ARQChapter 11 Link-Level Flow and Error Control31無差錯停止等待我們的目的是求出使用停止等待協(xié)議時一條線路上的最大幀發(fā)送速率，假定無差錯發(fā)生從A到B以一系列定長幀F(xiàn)1,F2,Fn的形式發(fā)送一個長報文的過程如下：A發(fā)送F1，B發(fā)送一個確認(rèn)A發(fā)送F2，B發(fā)送一個確認(rèn)A發(fā)送Fn，B發(fā)送一個確認(rèn)Chapter 11 Link-Level Flow and Error Control32發(fā)送數(shù)據(jù)的總時間可表達(dá)為nT，其中T是發(fā)送一個幀和收到一個確認(rèn)并準(zhǔn)備好發(fā)送下一個幀的時間T = Tframe + Tprop + Tp

19、roc + Tack + Tprop + Tproc其中：Tframe = 傳送一幀的時間 Tprop = 兩個站之間的傳播時延 Tproc = 每個站對一個到來的事件做出反應(yīng)的處理時延 Tack = 傳送一個確認(rèn)的時間假設(shè)處理時間可忽略，確認(rèn)幀比數(shù)據(jù)幀小得多 T Tframe + 2TpropChapter 11 Link-Level Flow and Error Control33Figure 11.4Chapter 11 Link-Level Flow and Error Control34吞吐量 = 1/T = 1/(Tframe + 2Tprop) 幀/sec以鏈路數(shù)據(jù)率規(guī)格化: 1

20、/ Tframe 幀/sec S = 1/(Tframe + 2Tprop) = Tframe = 1 1/ Tframe Tframe + 2Tprop 1 + 2a這里 a = Tprop / TframeS就是使用停止等待技術(shù)的鏈路的最大可能歸一化吞吐量，由于幀包含開銷位，有效吞吐量只會更低如果Tprop和Tframe都是常數(shù)，則參數(shù)a就是一個常數(shù)；這個條件通常能夠成立，因為通常除了一個序列中的最后一幀，其他幀都是固定長度的，而對于點到點的鏈路，傳播時延是一個常量Chapter 11 Link-Level Flow and Error Control35有差錯的停止等待ARQ如前，成功發(fā)

21、送一幀的時間是(Tframe + 2Tprop)如果一個幀丟失或它的ACK丟失，并假設(shè)傳送成功需兩次傳輸，則幀的傳輸時間為 T= Tframe + Timeout + Tframe + 2Tprop假定超時時間值等于兩倍的傳播時延值，則 T=2(Tframe + 2Tprop)定義Nx是每個幀需要傳輸?shù)钠骄螖?shù)，那么 T=Nx(Tframe + 2Tprop)歸一化吞吐量：S = 1 Nx (1 + 2a)Chapter 11 Link-Level Flow and Error Control36設(shè)P = 單個幀出錯的概率，并假定ACK從不出錯，則于是得到有差錯停止等待的吞吐量： Chapte

22、r 11 Link-Level Flow and Error Control37參數(shù)aa = 傳播時間 = d/V = Rd 傳輸時間 L/R VL 這里：d = 兩站間鏈路的距離 V = 信號沿鏈路傳播的速度 L = 幀的長度，以位計 R = 鏈路的數(shù)據(jù)率，單位是bpsa在評價各種鏈路控制方案的性能方面很有用，它對影響性能的各種因素提供了深刻的解釋對于固定長度的幀，a與數(shù)據(jù)率乘以媒體長度成正比；看待a的一種有用的方式是將它看做代表了以位計數(shù)的媒體長度與幀長的比率Chapter 11 Link-Level Flow and Error Control38Chapter 11 Link-Leve

23、l Flow and Error Control39幾個例子ATM廣域網(wǎng)：兩個站之間的距離是1000 km；標(biāo)準(zhǔn)ATM信元大小為424 bit；標(biāo)準(zhǔn)數(shù)據(jù)率155.52 Mbps；光纖的傳播速度2*108 m/s 可以求得a=1850，歸一化吞吐量只有0.00027LAN：距離從0.1 km到10 km，數(shù)據(jù)率從10 Mbps到1 Gbps，假定V= 2*108 m/s；幀大小是1000 bit，數(shù)據(jù)率為10 Mbps a為0.005-0.5，而吞吐量在0.5-0.991之間；對于100 Mbps的LAN，可以得到差不多的利用率可以看到LAN通常效率相當(dāng)高，而高速廣域網(wǎng)則效率不高Chapter

24、11 Link-Level Flow and Error Control40幾個例子(續(xù))通過Modem在話音質(zhì)量的線路上進行的數(shù)字?jǐn)?shù)據(jù)傳輸：通常的數(shù)據(jù)率為28.8 kbps，仍然考慮1000 bit的幀長，鏈路距離可以從幾十m到幾千km，如果選取距離d=1000 m，可求出a為1.44*10-4，而歸一化吞吐量約等于1；即使選取d=5000km，可求出a為0.72，歸一化吞吐量為0.4表11.1列出a的若干取值ISDN的64 kbps鏈路幀中繼網(wǎng)絡(luò)鏈路LAN鏈路Chapter 11 Link-Level Flow and Error Control41Table 11.1Chapter 11

25、 Link-Level Flow and Error Control42停止等待再討論在數(shù)據(jù)率很高和發(fā)送端與接收端距離很遠(yuǎn)的情況下，停止等待流量控制的線路利用率不高為了觀察a對于歸一化吞吐量的影響，可以將S=(1-P)/(1+2a)畫出來雖然S的值依賴于P，但P在很寬的取值范圍里對結(jié)果都沒有太大影響，我們隨便選取P=10-3從圖中看到：當(dāng)a1時，吞吐量嚴(yán)重降低；當(dāng)a10時，停止等待的效率如此之低，以至于它變得沒有什么用途Chapter 11 Link-Level Flow and Error Control43Figure 11.9Chapter 11 Link-Level Flow and

26、Error Control44無差錯滑動窗ARQ對于滑動窗流量控制來說，線路的吞吐量取決于窗口的大小W和a的值將幀傳輸時間歸一化為1，故傳播時延就是a情況 1: W 2a + 1對幀1的確認(rèn)在A消耗完其窗口前就到達(dá)了A，因此A可以不停地連續(xù)傳輸，而歸一化吞吐量是1情況 2: W 2a +1A 在t = W 時刻就耗盡了它的窗口，因此直到t = 2a + 1時刻前都不能再發(fā)送幀Chapter 11 Link-Level Flow and Error Control45Figure 11.10Chapter 11 Link-Level Flow and Error Control46規(guī)格化吞吐量

27、1 W 2a + 1 S = W W 2a +1 2a + 1 Chapter 11 Link-Level Flow and Error Control47滑動窗吞吐量與a的關(guān)系通常序號是用一個n位字段提供的，這時最大窗口大小是W=2n-1圖11.11示出了窗口大小是1，7和127時最大吞吐量與a的關(guān)系W=1對應(yīng)于停止等待W=7對于許多應(yīng)用就足夠了W=127可用于較大的a值(如高速廣域網(wǎng)的情況)Chapter 11 Link-Level Flow and Error Control48Figure 11.11Chapter 11 Link-Level Flow and Error Contro

28、l49拒選ARQ對于拒選ARQ，可以使用在停止等待ARQ上使用的相同的推導(dǎo)，即，將無差錯的方程式除以Nx，而且仍有Nx=1/(1-P) 1 - P W 2a + 1 S = W(1 - P) W 2a +1 2a + 1 Chapter 11 Link-Level Flow and Error Control50Go-Back-N ARQ使用類似的推導(dǎo)，但在計算Nx的近似值時有所不同，每個差錯都要求重傳K幀而不是僅僅一幀，因此其中f(i)是如果原來的幀必須傳輸i次所傳輸?shù)目値瑪?shù)，為：f(i)=1+(i-1)K=(1-K)+KiChapter 11 Link-Level Flow and Error Control51Go-Back-N ARQ(續(xù))由上面公式代換得到：研究圖11.10，可以得到：Chapter 11 Link-Level Flow and Error Control52Chapter 11 Link-Level Flow and Error Control53Go-Back-N ARQ(續(xù)) 1 - P W 2a + 1 S = 1 + 2aP W(1 - P)