計(jì)算機(jī)網(wǎng)絡(luò)課程詳細(xì)3

1、第三章 數(shù)據(jù)鏈路層1 組幀（framing）z使用字節(jié)（字符）填充的首尾標(biāo)記法：y使用特殊的字節(jié)來表示幀的開始與結(jié)束y為避免在數(shù)據(jù)部分出現(xiàn)這些特殊字節(jié)時(shí)產(chǎn)生異義，在特殊字節(jié)前插入轉(zhuǎn)義字符，稱為字節(jié)填充（byte stuffing）y該方法依賴于特定的字符編碼集，幀長必須是8比特的整倍數(shù)，靈活性差，處理開銷大（必須由軟件處理）。字節(jié)填充圖例(a) A frame delimited by flag bytes(b) Four examples of byte sequences before and after stuffing.比特填充圖例(a) The original data.(b) T

2、he data as they appear on the line.(c) The data as they are stored in receivers memory after destuffing.2 檢錯和糾錯z傳輸出錯的類型y單個(gè)錯：由隨機(jī)的信道熱噪聲引起，一次只影響1位。y突發(fā)錯：由瞬間的脈沖噪聲引起，一次影響許多位。用突發(fā)長度表示突發(fā)錯影響的最大數(shù)據(jù)位數(shù)。z差錯編碼的類型y檢錯碼：只能檢測到數(shù)據(jù)傳輸發(fā)生了錯誤，但無法自行糾正，通常與反饋重傳結(jié)合起來進(jìn)行差錯恢復(fù)。y糾錯碼：不權(quán)能夠檢測出數(shù)據(jù)傳輸發(fā)生了錯誤，而且能夠自行糾正錯誤。如何檢測與糾正錯誤？z 碼字（codeword）：

3、由m比特的數(shù)據(jù)（消息）加上r比特的冗余（校驗(yàn)位）構(gòu)成。z 有效編碼集：由2m個(gè)（符合編碼規(guī)則的）有效碼字組成。z 檢錯：當(dāng)收到的碼字為無效碼字時(shí)，稱檢測出錯誤。z 海明距離（Hamming Distance）：兩個(gè)碼字的對應(yīng)位上取值不同的位數(shù)。z 糾錯：將收到的無效碼字糾正到距其最近的有效碼字。z 檢錯碼與糾錯碼的能力都是有限的。2.2 循環(huán)冗余碼（CRC碼）z CRC是一種多項(xiàng)式編碼，它將位串看成是某個(gè)一元多項(xiàng)式的系數(shù)，如1011001看成是一元多項(xiàng)式X6 + X4 + X3 + 1的系數(shù)。z 信息多項(xiàng)式M(x)：由m個(gè)信息比特為系數(shù)構(gòu)成的多項(xiàng)式。z 冗余多項(xiàng)式R(x)：由r個(gè)冗余比特為系數(shù)

4、構(gòu)成的多項(xiàng)式。z 碼多項(xiàng)式T(x)：在m個(gè)信息比特后加上r個(gè)冗余比特構(gòu)成的碼字所對應(yīng)的多項(xiàng)式，表達(dá)式為T(x) = xrM(x) + R(x)。z 生成多項(xiàng)式G(x)：雙方預(yù)先確定用來計(jì)算R(x)的一個(gè)多項(xiàng)式。z 編碼方法：用對應(yīng)于G(x)的位串去除對應(yīng)于xrM(x)的位串，所得的余式即為R(x)，將其附加到信息比特串的后面一起發(fā)送。z 檢錯方法：用對應(yīng)于G(x)的位串去除對應(yīng)于T(x)的位串，若余式為0則認(rèn)為傳輸正確，否則認(rèn)為傳輸錯誤。z CRC碼檢錯能力強(qiáng)，實(shí)現(xiàn)簡單快捷，是應(yīng)用最廣泛的檢錯碼。CRC編碼及校驗(yàn)z 例1：G(X) = X4 + X + 1，對10110011進(jìn)行CRC編碼，為

5、101100110100。z 例2：仍取G(X) = X4 + X + 1，判斷收到的位串100101111001是否有錯？ 3 可靠交付z差錯恢復(fù)的兩種辦法：y使用糾錯碼，由接收端自動糾正錯誤。y使用檢錯碼，采用自動重傳請求（ARQ）保證可靠交付。這是數(shù)據(jù)鏈路層（及傳輸層）上最常使用的可靠交付方式。z自動重傳請求（Automatic Repeat Request）：y使用確認(rèn)和超時(shí)實(shí)現(xiàn)可靠傳輸?shù)牟呗浴兩種ARQ方案：y停-等算法y滑動窗口算法3.1 停-等算法（stop-and-wait）z 基本思想：y發(fā)送方發(fā)完一幀后即停下來等待確認(rèn)，同時(shí)啟動一個(gè)定時(shí)器；y如果收到確認(rèn)，復(fù)位定時(shí)器，發(fā)送

6、下一個(gè)幀；y如果定時(shí)器超時(shí)，重發(fā)剛才的幀。z 停-等算法的四種情形。z 停-等算法的超時(shí)值對性能影響很大，必須仔細(xì)選擇。z 為區(qū)分新幀和重發(fā)幀，停-等算法使用一比特的幀序號。停-等算法的四種情形停-等算法的處理流程發(fā)送端：1）幀序號seq初始化為0。2）從緩沖區(qū)中取出一個(gè)幀，以seq作為幀序號發(fā)送。3）啟動定時(shí)器，等待確認(rèn)： i）收到確認(rèn)幀，且seqack，則seq加1；從緩沖區(qū)中取出一個(gè)新的幀，加上seq發(fā)送。 ii）收到確認(rèn)幀，但seq = ack，重發(fā)當(dāng)前序號的幀。 iii）收到錯誤的確認(rèn)幀，重發(fā)當(dāng)前序號的幀。 iv）定時(shí)器超時(shí)，重發(fā)當(dāng)前序號的幀。4）回到3） 接收端：1）幀序號ack初

7、始化為0，準(zhǔn)備接收序號為0的幀。 2）等待接收。 3）幀到達(dá)，有以下三種情況： i）幀校驗(yàn)正確，且seq = ack，將幀存入接收緩沖區(qū)；ack 加 1，放入確認(rèn)幀中發(fā)送，確認(rèn)幀中的序號表明當(dāng)前期待接收的幀。 ii）幀校驗(yàn)正確，但seqack，丟棄幀，重發(fā)確認(rèn)幀。 iii）幀校驗(yàn)錯誤，丟棄幀，重發(fā)確認(rèn)幀。4）回到2）停-等算法的處理流程發(fā)送端：1）幀序號seq初始化為0。2）從緩沖區(qū)中取出一個(gè)幀，以seq作為幀序號發(fā)送。3）啟動定時(shí)器，等待確認(rèn)： i）收到確認(rèn)幀，且seqack，seq加1；從緩沖區(qū)中取出一個(gè)新的幀，加上seq發(fā)送。 ii）其它情況，重發(fā)當(dāng)前序號的幀。4）回到3） 接收端：1）

8、幀序號ack初始化為0。 2）等待接收。 3）幀到達(dá)： i）幀校驗(yàn)正確，且seq = ack，將幀存入接收緩沖區(qū)；ack 加 1，放入確認(rèn)幀中發(fā)送。 ii）其它情況，丟棄幀，重發(fā)確認(rèn)幀。4）回到2）3.2 滑動窗口（sliding window）z滑動窗口的本質(zhì)是，發(fā)送端在收到確認(rèn)之前可以發(fā)送多個(gè)幀。z問題：y某個(gè)幀出錯或丟失怎么處理？x接收端是否接收后續(xù)幀？x發(fā)送端只重發(fā)出錯幀，還是重發(fā)從出錯幀開始的所有后續(xù)幀？x若只重發(fā)出錯幀，幀的順序如何保證？y發(fā)送端一次可以發(fā)送多少個(gè)幀？滑動窗口協(xié)議的功能z滑動窗口是計(jì)算機(jī)網(wǎng)絡(luò)中最著名的算法之一，它可以應(yīng)用在數(shù)據(jù)鏈路層及傳輸層，用來完成三個(gè)不同的任務(wù)：

9、y在不可靠的鏈路（網(wǎng)絡(luò)）上可靠地傳輸數(shù)據(jù)y保持?jǐn)?shù)據(jù)的傳輸順序y支持流量控制z在數(shù)據(jù)鏈路層上，以上三個(gè)功能組合在一個(gè)滑動窗口協(xié)議中。發(fā)送窗口的概念z 發(fā)送窗口：包含一組幀序號，這些幀已發(fā)送但尚未被確認(rèn)。z 發(fā)送窗口的三個(gè)要素：y窗口下沿：最早發(fā)送但尚未被確認(rèn)的幀。y窗口上沿：最近發(fā)送的幀。y窗口的最大值：一次最多允許發(fā)送的幀數(shù)。z 發(fā)送窗口如何變化：y窗口未達(dá)到最大值，且要發(fā)送一個(gè)新的幀時(shí)，窗口上沿向前推進(jìn)一個(gè)序號（序號加1后模2n）。y收到窗口下沿幀的確認(rèn)時(shí)，窗口下沿向前推進(jìn)一個(gè)序號（將已被確認(rèn)的幀移出發(fā)送窗口）。z 發(fā)送窗口中的幀都保留在緩沖區(qū)里以備重傳，當(dāng)某個(gè)幀被移出發(fā)送窗口時(shí)，同時(shí)從緩沖

10、區(qū)中刪除。發(fā)送窗口和接收窗口圖示接收窗口的概念z 接收窗口：允許接收的幀序號。凡落在接收窗口內(nèi)的幀必須接收，落在窗口外的幀被丟棄。z 接收窗口的大?。汗潭ú蛔儯偸潜３殖跏紩r(shí)的大小。z 接收窗口如何變化：y當(dāng)窗口下沿幀被正確接收后，窗口整體向前滑動一個(gè)序號。z 數(shù)據(jù)鏈路層什么時(shí)候?qū)f交到網(wǎng)絡(luò)層？y僅當(dāng)窗口下沿幀正確接收后，鏈路層才將幀遞交給網(wǎng)絡(luò)層，因此幀總是按順序被遞交到網(wǎng)絡(luò)層。捎帶確認(rèn)（piggybacking）z 捎帶確認(rèn)：y在雙向通信過程中，接收端可以將確認(rèn)序號攜帶在數(shù)據(jù)幀中傳輸，提高傳輸效率。z 捎帶確認(rèn)帶來的問題：y當(dāng)需要發(fā)送確認(rèn)時(shí)數(shù)據(jù)尚未準(zhǔn)備好，怎么辦？z 推遲確認(rèn)：y讓確認(rèn)信息

11、推遲一小段時(shí)間再發(fā)送；若數(shù)據(jù)仍未準(zhǔn)備好，接收端發(fā)送一個(gè)單獨(dú)的確認(rèn)幀。z 推遲確認(rèn)帶來的問題：y如何對正確收到的若干個(gè)幀同時(shí)進(jìn)行確認(rèn)？z 接收端通常用對某一個(gè)幀的確認(rèn)來表示對該幀之前的所有幀進(jìn)行確認(rèn)。這也解釋了為什么接收端僅當(dāng)收到窗口下沿幀的時(shí)候才能發(fā)送確認(rèn)。兩種滑動窗口協(xié)議z 問題：y 當(dāng)采用滑動窗口技術(shù)連續(xù)發(fā)送很多幀時(shí)，如果某個(gè)幀出現(xiàn)了傳輸錯誤怎么處理？z 兩種解決方案：y 回退 n幀（go back n）y 選擇重傳（selective repeat）選擇重傳z 設(shè)計(jì)思想：y當(dāng)接收端收到一個(gè)出錯幀或亂序幀時(shí)，后續(xù)到達(dá)的幀只要校驗(yàn)正確且落在接收窗口內(nèi)，都放入接收緩沖區(qū)中；y發(fā)送端超時(shí)后只重傳

12、最早發(fā)送但未被確認(rèn)的幀。z 該策略對應(yīng)接收窗口大于1的情況。z 加快重傳：y選擇重傳通常使用一個(gè)否定的確認(rèn)（NAK）對校驗(yàn)出錯或丟失的幀進(jìn)行確認(rèn)，以便發(fā)送端盡快重傳該幀。z 當(dāng)接收窗口很大時(shí)，這種方法要求接收端有較大的內(nèi)存，但它不浪費(fèi)帶寬。選擇重傳示意圖幀的序號空間與發(fā)送窗口大小z 發(fā)送窗口的最大值受制于哪些因素？y接收端處理能力（與接收端有關(guān)）y延遲-帶寬乘積（與信道有關(guān)）y幀的序號空間（與協(xié)議有關(guān)）（）z 問題：y給定幀的序號空間，如何設(shè)置發(fā)送窗口的大小才能避免因序號重用出現(xiàn)的混亂？z 對于給定的幀序號空間，不同滑動窗口協(xié)議的發(fā)送窗口大小有不同的限制。Go Back n的發(fā)送窗口最大值z

13、使用Go Back n協(xié)議，發(fā)送窗口的大小不能超過2n-1。z 用一個(gè)反例說明：若n = 3，發(fā)送窗口大小取為23 = 8，考慮如下情形：y發(fā)送方連續(xù)發(fā)送序號從07的8個(gè)幀，等待確認(rèn)；y接收方正確收到這8個(gè)幀，對最大序號7進(jìn)行確認(rèn)；y發(fā)送方有兩種情況：x收到確認(rèn)，發(fā)送序號為07的8個(gè)新幀；x因確認(rèn)丟失而超時(shí)，重發(fā)8個(gè)老幀；y接收方無法判斷收到的是8個(gè)新幀還是重發(fā)的8個(gè)老幀。Go Back n的發(fā)送窗口大小（續(xù)）z 若發(fā)送窗口大小取為7，以上問題不會發(fā)生：y發(fā)送方發(fā)送序號從06的7個(gè)幀，等待確認(rèn)；y接收方正確收到這7個(gè)幀，對最大序號6進(jìn)行確認(rèn)，并準(zhǔn)備接收序號為7的幀（接收窗口僅包含序號7）；y發(fā)

14、送方有兩種情況：x收到確認(rèn)，發(fā)送序號為7及05的7個(gè)新幀；x因確認(rèn)丟失超時(shí)，重發(fā)序號為06的7個(gè)老幀；y接收方處理：x收到序號為7的幀，表明這一批是新幀，接收，對序號5確認(rèn)；x沒有收到序號為7的幀（重傳幀，或是序號為7的幀丟失），不予接收，重發(fā)對序號6的確認(rèn)。y發(fā)送方處理：x確認(rèn)序號在發(fā)送窗口內(nèi)：取下一批數(shù)據(jù)幀發(fā)送；x確認(rèn)序號不在發(fā)送窗口內(nèi)或超時(shí)：重傳發(fā)送窗口內(nèi)的幀。選擇重傳協(xié)議的發(fā)送窗口大小z 使用選擇重傳協(xié)議，若發(fā)送窗口與接收窗口大小相同，則發(fā)送窗口的大小不能超過2n-1。z 用一個(gè)反例說明：若n = 3，且發(fā)送窗口大小取為7，考慮以下情形：y發(fā)送方：連續(xù)發(fā)送序號從06的7個(gè)幀，等待確認(rèn)；

15、y接收方：正確收到這7個(gè)幀，對序號6進(jìn)行確認(rèn)，并準(zhǔn)備接收序號為7和05的幀（接收窗口中包含序號7、05）；y確認(rèn)丟失，發(fā)送方超時(shí)后重發(fā)序號為0的幀；y接收方：幀0落在接收窗口內(nèi)，接收下來，并發(fā)送NAK 7；y發(fā)送方：收到NAK 7，知道06的7個(gè)幀已全部收到，另取7個(gè)新幀，編號為7和05，發(fā)送；y接收方：丟棄序號為0的幀，接收其余的5個(gè)幀。選擇重傳協(xié)議的發(fā)送窗口大?。ɡm(xù)）z若發(fā)送窗口大小取為4，以上問題不會發(fā)生：y發(fā)送方：發(fā)送序號從03的4個(gè)幀，等待確認(rèn)；y接收方：正確收到這4個(gè)幀，對序號3進(jìn)行確認(rèn)，并準(zhǔn)備接收序號為47的幀（接收窗口包含序號47）；y確認(rèn)丟失，發(fā)送方超時(shí)后重發(fā)序號為0的幀；y

16、接收方：幀0不在接收窗口內(nèi)，丟棄，發(fā)送NAK 4；y發(fā)送方：收到NAK 4，知道03已全部收到，另取4個(gè)新幀，編號為47，發(fā)送；y接收方：接收序號為47的幀。滑動窗口的總結(jié)（1）z 使用前提：信號傳播延遲遠(yuǎn)大于幀的發(fā)送時(shí)間。z 從實(shí)現(xiàn)的角度看，發(fā)送窗口相當(dāng)于維護(hù)了一個(gè)環(huán)形的發(fā)送緩沖區(qū)：yhead為窗口上沿ytail為窗口下沿y環(huán)的大小等于幀的序號空間z 窗口操作：y發(fā)送一個(gè)幀：移動head，將幀插入head的位置；y收到tail幀的確認(rèn)：移動tail，釋放緩沖空間；y當(dāng)head與tail之間只有一個(gè)空閑緩沖區(qū)時(shí)：停止發(fā)送。滑動窗口的總結(jié)（2）z 從實(shí)現(xiàn)的角度看，接收窗口相當(dāng)于維護(hù)了一個(gè)環(huán)形的接

17、收緩沖區(qū)：ytail為窗口下沿yhead為窗口上沿y環(huán)的大小等于幀的序號空間z 窗口操作：y收到一個(gè)幀：放入從head至tail之間的對應(yīng)緩沖區(qū)中；y收到tail幀：將從tail開始的連續(xù)k個(gè)幀交給網(wǎng)絡(luò)層，head和tail同時(shí)向前移動k個(gè)位置?；瑒哟翱诘目偨Y(jié)（3）z滑動窗口與停-等算法：y停-等算法可以看成是發(fā)送窗口和接收窗口均為1的滑動窗口算法；y滑動窗口要處理的問題比停-等算法復(fù)雜得多：x幀的亂序問題x發(fā)送端一次可以發(fā)送多少幀？5.1 High-level Data Link Control z 幀結(jié)構(gòu)：y標(biāo)志：01111110，標(biāo)識一幀的開始與結(jié)束，以及作為幀間填充。y地址：在點(diǎn)到多點(diǎn)

18、線路中用于指明通信的終端地址，在點(diǎn)到點(diǎn)線路中用于區(qū)分命令和響應(yīng)。y控制：用于構(gòu)成各種命令和響應(yīng)，對鏈路進(jìn)行監(jiān)控。y信息：可以是任意的二進(jìn)制比特串。y校驗(yàn)：CRC碼，對兩個(gè)標(biāo)志之間的幀內(nèi)容進(jìn)行校驗(yàn)。幀類型z 信息幀（Information frame）：y以控制字段的第一比特為“0”標(biāo)志。y用于傳送數(shù)據(jù)，數(shù)據(jù)放在信息字段中。y采用滑動窗口協(xié)議，N(S)為發(fā)送序號，N(R)為捎帶確認(rèn)的序號。HDLC的訪問規(guī)程z鏈路層的操作分為三個(gè)階段：y建立鏈路：一方發(fā)送一個(gè)置模式命令，另一方發(fā)送UA幀進(jìn)行響應(yīng)，并初始化鏈路變量。y傳輸信息：x雙方使用滑動窗口協(xié)議進(jìn)行數(shù)據(jù)傳輸控制；x對收到的信息幀使用捎帶確認(rèn)或監(jiān)視幀進(jìn)行響應(yīng)；x對檢測到錯誤的幀使用否定確認(rèn)或選擇拒絕要求重發(fā)；x未準(zhǔn)備好接收下一幀時(shí)，用接收未準(zhǔn)備好暫停對方的發(fā)送。y斷開鏈路：一方發(fā)送一個(gè)斷連命令，另一方用一個(gè)UA幀進(jìn)行響應(yīng)。PPP協(xié)議的組成zPPP由以下三部分組成：y一種在串行通信線路上的組幀方式，用于區(qū)分幀的邊界，并可支持差錯檢測。y一個(gè)用于建立、配置、測試和拆除數(shù)據(jù)鏈路的鏈路控制協(xié)議LCP。y一組網(wǎng)絡(luò)控制協(xié)議（NCP），用以支持