點(diǎn)到點(diǎn)信道的數(shù)據(jù)鏈路層課件

第三章點(diǎn)到點(diǎn)信道的數(shù)據(jù)鏈路層本章主要內(nèi)容停止等待協(xié)議連續(xù)ARQ協(xié)議因特網(wǎng)的點(diǎn)對(duì)點(diǎn)協(xié)議PPP第三章點(diǎn)到點(diǎn)信道的數(shù)據(jù)鏈路層本章主要內(nèi)容停止等待協(xié)議3.1數(shù)據(jù)鏈路層的基本概念

局域網(wǎng)廣域網(wǎng)主機(jī)

H1主機(jī)

H2路由器

R1路由器

R2路由器

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

H1

向

H2

發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從層次上來看數(shù)據(jù)的流動(dòng)3.1.1數(shù)據(jù)鏈路層的簡(jiǎn)單模型3.1數(shù)據(jù)鏈路層的基本概念

局域網(wǎng)廣域網(wǎng)主機(jī)H1主機(jī)(a)數(shù)據(jù)鏈路層結(jié)點(diǎn)A結(jié)點(diǎn)B幀(b)發(fā)送幀接收鏈路IP數(shù)據(jù)報(bào)1010……0110幀取出數(shù)據(jù)鏈路層網(wǎng)絡(luò)層鏈路結(jié)點(diǎn)A結(jié)點(diǎn)B物理層IP數(shù)據(jù)報(bào)1010……0110幀裝入數(shù)據(jù)鏈路層傳送的是幀(a)數(shù)據(jù)結(jié)點(diǎn)A結(jié)點(diǎn)B幀(b)發(fā)送幀接收鏈路IP數(shù)據(jù)報(bào)3.1.2鏈路和數(shù)據(jù)鏈路

鏈路(link)即物理鏈路，是從一個(gè)結(jié)點(diǎn)到相鄰結(jié)點(diǎn)的一段物理線路，中間沒有任何其他的交換結(jié)點(diǎn)。一條鏈路只是一條路徑的一個(gè)組成部分。數(shù)據(jù)鏈路(datalink)即邏輯鏈路，除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路。現(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來實(shí)現(xiàn)這些協(xié)議的硬件和軟件。一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層的功能。

3.1.2鏈路和數(shù)據(jù)鏈路鏈路(link)即物理鏈路，是3.2三個(gè)基本問題

(1)幀定界(2)透明傳輸(3)差錯(cuò)控制

3.2三個(gè)基本問題(1)幀定界3.2.1幀定界幀定界(framing)就是確定幀的界限。

幀結(jié)束幀首部IP數(shù)據(jù)報(bào)幀的數(shù)據(jù)部分幀尾部

MTU數(shù)據(jù)鏈路層的幀長(zhǎng)從這里開始發(fā)送幀開始3.2.1幀定界幀定界(framing)就是確定幀的界限用控制字符進(jìn)行幀定界的方法舉例

SOH裝在幀中的數(shù)據(jù)部分幀幀開始符幀結(jié)束符發(fā)送在前EOT用控制字符進(jìn)行幀定界的方法舉例SOH裝在幀中的數(shù)據(jù)部分幀幀3.2.2透明傳輸SOHEOT出現(xiàn)了“EOT”被接收端當(dāng)作無效幀而丟棄被接收端誤認(rèn)為是一個(gè)幀數(shù)據(jù)部分EOT完整的幀發(fā)送在前3.2.2透明傳輸SOHEOT出現(xiàn)了“EOT”被接收端當(dāng)SOHSOHESCSOHEOTESCESCzESCyESCzESCx原始數(shù)據(jù)EOTEOT經(jīng)過字節(jié)填充后發(fā)送的數(shù)據(jù)字節(jié)填充字節(jié)填充字節(jié)填充字節(jié)填充發(fā)送在前幀開始符幀結(jié)束符用字節(jié)填充法解決透明傳輸?shù)膯栴}

SOHSOHESCSOHEOTESCESCzESCyESCz3.2.3差錯(cuò)檢測(cè)檢錯(cuò)奇偶校驗(yàn)循環(huán)冗余校驗(yàn)（CRC）3.2.3差錯(cuò)檢測(cè)檢錯(cuò)奇偶校驗(yàn)循環(huán)冗余校驗(yàn)（CRC）

奇/偶校驗(yàn)的規(guī)則是在原數(shù)據(jù)位后附加一個(gè)校驗(yàn)位，將其值置為“0”或“1”，使附加該位后的整個(gè)數(shù)據(jù)碼中“1”的個(gè)數(shù)成為奇數(shù)或偶數(shù)。使用奇數(shù)個(gè)“1”進(jìn)行校驗(yàn)的方案被稱為奇校驗(yàn)；對(duì)應(yīng)于偶數(shù)個(gè)“1”的校驗(yàn)方案被稱為偶校驗(yàn)。奇/偶校驗(yàn)奇/偶校驗(yàn)的規(guī)則是在原數(shù)據(jù)位后附加一個(gè)校驗(yàn)位，將其值循環(huán)冗余檢驗(yàn)在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn)CRC的檢錯(cuò)技術(shù)。在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組k位。假設(shè)待傳送的一組數(shù)據(jù)M=101001（現(xiàn)在k=6）。我們?cè)贛的后面再添加供差錯(cuò)檢測(cè)用的r位冗余碼一起發(fā)送。

循環(huán)冗余檢驗(yàn)在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗(yàn)①設(shè)f（x）為k階信息碼多項(xiàng)式，G（x）為r階生成碼多項(xiàng)式；②用模2除法進(jìn)行xrf（x）/G（x），得到余式R（x），R（x）為r階冗余碼多項(xiàng)式；③用模2減法進(jìn)行xrf（x）-R（x），得到待傳送的CRC碼多項(xiàng)式。CRC碼的計(jì)算過程：①設(shè)f（x）為k階信息碼多項(xiàng)式，G（x）為r階生成碼多項(xiàng)式例如，已知要傳送的信息為1010001101，G(X)=X5+X4+X2+1，計(jì)算冗余碼的過程和結(jié)果如下：∴傳送序列T(x)=101000110101110例如，已知要傳送的信息為1010001101，G(X)=X5接收端對(duì)收到的每一幀進(jìn)行CRC檢驗(yàn)

接收方收到后，用G(x)除多項(xiàng)式，若余數(shù)R

0，則傳輸有錯(cuò),就丟棄。若得出的余數(shù)R=0，則判定這個(gè)幀沒有差錯(cuò)，就接受(accept)。但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。

接收端對(duì)收到的每一幀進(jìn)行CRC檢驗(yàn)接收方收到后，用G(思考：

習(xí)題3-17思考：注意

僅用循環(huán)冗余檢驗(yàn)CRC差錯(cuò)檢測(cè)技術(shù)只能做到無差錯(cuò)接受(accept)?！盁o差錯(cuò)接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們都能以非常接近于1的概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯(cuò)”。也就是說：“凡是接收端數(shù)據(jù)鏈路層接受的幀都沒有傳輸差錯(cuò)”（有差錯(cuò)的幀就丟棄而不接受）。要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認(rèn)和重傳機(jī)制。注意僅用循環(huán)冗余檢驗(yàn)CRC差錯(cuò)檢測(cè)技術(shù)只能做到無差錯(cuò)接3.3停止等待協(xié)議兩臺(tái)計(jì)算機(jī)通過一條數(shù)據(jù)鏈路進(jìn)行通信的簡(jiǎn)化模型假定１：鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。假定２：不管發(fā)送方以多快的速率發(fā)送數(shù)據(jù)，接收方總是來得及收下，并及時(shí)上交主機(jī)。3.3停止等待協(xié)議兩臺(tái)計(jì)算機(jī)通過一條數(shù)據(jù)鏈路進(jìn)行通信的具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議B具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議B算法發(fā)送結(jié)點(diǎn)：(1)從主機(jī)取一個(gè)數(shù)據(jù)幀；(2)將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存；(3)將發(fā)送緩存中的數(shù)據(jù)發(fā)送出去；(4)等待；(5)若收到由接收結(jié)點(diǎn)發(fā)過來的信息，則從主機(jī)取一個(gè)新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)算法發(fā)送結(jié)點(diǎn)：算法接收結(jié)點(diǎn)：(1)等待；(2)若收到由發(fā)送結(jié)點(diǎn)發(fā)過來的數(shù)據(jù)幀,則將其放入數(shù)據(jù)鏈路層的接收緩存；(3)將接收緩存中的數(shù)據(jù)幀上交主機(jī)；(4)向發(fā)送結(jié)點(diǎn)發(fā)一信息,表示數(shù)據(jù)幀已上交主機(jī)；(5)轉(zhuǎn)到(1)算法接收結(jié)點(diǎn)：3.3.1停止等待協(xié)議的工作原理數(shù)據(jù)幀出錯(cuò)確認(rèn)幀出錯(cuò)ACKn表示“第n–1號(hào)幀已經(jīng)收到，現(xiàn)在期望接收第n號(hào)幀”。正常情況ACK1ACK03.3.1停止等待協(xié)議的工作原理數(shù)據(jù)幀出錯(cuò)確認(rèn)幀出錯(cuò)A

發(fā)送結(jié)點(diǎn)：(1)從主機(jī)取一個(gè)數(shù)據(jù)幀，送交發(fā)送緩存。(2)V(S)←0。(發(fā)送狀態(tài)變量的初始化)(3)N(S)←V(S)。(發(fā)送序號(hào)N(S))(4)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。(5)設(shè)置超時(shí)計(jì)時(shí)器。(6)等待。{等待以下(7)和(8)中最先出現(xiàn)的一個(gè)}(7)收到確認(rèn)幀ACKn，若n=1–V(s)，則：從主機(jī)取一個(gè)新的數(shù)據(jù)幀，放入發(fā)送緩存；V(S)←[1

V(S)]，轉(zhuǎn)到(3)。否則，丟棄這個(gè)確認(rèn)幀，轉(zhuǎn)到(6)。(8)若超時(shí)計(jì)時(shí)器時(shí)間到，則轉(zhuǎn)到(4)。3.3.2停止等待協(xié)議的算法ACK1ACK0發(fā)送結(jié)點(diǎn)：3.3.2停止等待協(xié)議的算法ACK1AC接收結(jié)點(diǎn)：(1)V(R)←0。(接收狀態(tài)變量的初始化，值為預(yù)接收數(shù)據(jù)幀序號(hào))(2)等待。(3)收到一個(gè)數(shù)據(jù)幀；若N(S)=V(R)，則執(zhí)行(4)；否則丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到(6)。(4)將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件（也就是數(shù)據(jù)鏈路層模型中的主機(jī)）。(5)V(R)←[1

V(R)]。(6)n←V(R)；發(fā)送確認(rèn)幀ACKn，轉(zhuǎn)到(2)。ACK1ACK0接收結(jié)點(diǎn)：ACK1ACK0思考：

習(xí)題3-4思考：(1)在發(fā)送端,在發(fā)送數(shù)據(jù)之前,都必須將發(fā)送狀態(tài)變量V(S)的值寫到數(shù)據(jù)幀的發(fā)送序號(hào)N(S)上。(2)發(fā)送端在發(fā)送完數(shù)據(jù)幀時(shí),必須在其發(fā)送緩中暫時(shí)保留這個(gè)數(shù)據(jù)幀的副本。(3)在接收端只接受序號(hào)正確的數(shù)據(jù)幀,并發(fā)送確認(rèn)。停止等待協(xié)議的要點(diǎn)(1)在發(fā)送端,在發(fā)送數(shù)據(jù)之前,都必須將發(fā)送狀態(tài)變停止等待協(xié)在發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個(gè)數(shù)據(jù)幀。如果收到接收端發(fā)來的確認(rèn)幀，那么還可以繼續(xù)發(fā)送數(shù)據(jù)幀。要點(diǎn)：3.4發(fā)送窗口大于1的ARQ協(xié)議在發(fā)送完一個(gè)數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再01234523456DATAACK1ACK2ACK2ACK2ACK2ACK3ACK4tftout重傳送主機(jī)丟棄送主機(jī)出錯(cuò)時(shí)間AB3.4.1連續(xù)ARQ協(xié)議的工作原理01234發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口。發(fā)送窗口用來對(duì)發(fā)送端進(jìn)行流量控制。發(fā)送窗口的大小WT代表在還沒有收到對(duì)方確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個(gè)數(shù)據(jù)幀。3.4.2滑動(dòng)窗口的概念發(fā)送端和接收端分別設(shè)定發(fā)送窗口和接收窗口。3.4.2發(fā)送窗口的規(guī)則發(fā)送窗口內(nèi)的幀是允許發(fā)送的幀,而不考慮有沒有收到確認(rèn).(2)每發(fā)送完一個(gè)幀,允許發(fā)送的幀數(shù)就減1.(3)如果所允許發(fā)送的幀都發(fā)送完了,但還沒有收到任何確認(rèn),那就不能再發(fā)送任何幀了.(4)每收到一個(gè)幀的確認(rèn),發(fā)送窗口就向前(向右)滑動(dòng)一個(gè)幀的位置.發(fā)送窗口的規(guī)則發(fā)送窗口內(nèi)的幀是允許發(fā)送的幀,而不考慮發(fā)送窗口01234567012WT不允許發(fā)送這些幀允許發(fā)送5個(gè)幀(a)01234567012不允許發(fā)送這些幀還允許發(fā)送4個(gè)幀WT已發(fā)送(b)01234567012不允許發(fā)送這些幀WT已發(fā)送(c)01234567012不允許發(fā)送這些幀還允許發(fā)送3個(gè)幀WT已發(fā)送已發(fā)送并已收到確認(rèn)(d)發(fā)送窗口01234567012WT不允許發(fā)送這些幀允許發(fā)送在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)才允許將該數(shù)據(jù)幀收下。若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其丟棄。在連續(xù)ARQ協(xié)議中，接收窗口的大小WR

=1。只有當(dāng)收到的幀的序號(hào)與接收窗口一致時(shí)才能接收該幀。否則，就丟棄它。每收到一個(gè)序號(hào)正確的幀，接收窗口就向前（即向右方）滑動(dòng)一個(gè)幀的位置。同時(shí)發(fā)送對(duì)該幀的確認(rèn)。

接收窗口的規(guī)則在接收端只有當(dāng)收到的數(shù)據(jù)幀的發(fā)送序號(hào)落入接收窗口內(nèi)才允許將該不允許接收這些幀01234567012WR準(zhǔn)備接收0號(hào)幀(a)不允許接收這些幀01234567012WR準(zhǔn)備接收1號(hào)幀已收到(b)不允許接收這些幀01234567012WR準(zhǔn)備接收4號(hào)幀已收到(c)發(fā)ACK1不允許接收這些幀01234567012WR準(zhǔn)備接收0號(hào)幀發(fā)送方接收方幀1234567869ACKACKNAK10出錯(cuò)只重傳幀6選擇重傳ARQ協(xié)議的工作原理3.4.4選擇重傳ARQ協(xié)議發(fā)送方接收方幀1234567869ACKACKNAK10出錯(cuò)思考：習(xí)題3-11思考：無確認(rèn)的無連接服務(wù)有確認(rèn)的無連接服務(wù)有確認(rèn)的面向連接服務(wù)3.4.5數(shù)據(jù)鏈路層所提供的基本服務(wù)無確認(rèn)的無連接服務(wù)3.4.5數(shù)據(jù)鏈路層所提供的基本服務(wù)3.5點(diǎn)對(duì)點(diǎn)協(xié)議PPP

3.5.1點(diǎn)對(duì)點(diǎn)協(xié)議的特點(diǎn)現(xiàn)在全世界使用得最多的數(shù)據(jù)鏈路層協(xié)議是點(diǎn)對(duì)點(diǎn)協(xié)議PPP(Point-to-PointProtocol)。用戶使用撥號(hào)電話線接入因特網(wǎng)時(shí)，一般都是使用PPP協(xié)議。

3.5點(diǎn)對(duì)點(diǎn)協(xié)議PPP

3.5.1點(diǎn)對(duì)點(diǎn)協(xié)議的特用戶到ISP的鏈路使用PPP協(xié)議

用戶至因特網(wǎng)已向因特網(wǎng)管理機(jī)構(gòu)申請(qǐng)到一批IP地址ISP接入網(wǎng)PPP協(xié)議用戶到ISP的鏈路使用PPP協(xié)議用至因特網(wǎng)已向因特PPP協(xié)議應(yīng)滿足的需求

簡(jiǎn)單封裝成幀透明性多種網(wǎng)絡(luò)層協(xié)議多種類型鏈路差錯(cuò)檢測(cè)檢測(cè)活躍度（即檢測(cè)連接狀態(tài)）最大傳送單元（MTU）網(wǎng)絡(luò)層地址協(xié)商數(shù)據(jù)壓縮協(xié)商

PPP協(xié)議應(yīng)滿足的需求簡(jiǎn)單PPP協(xié)議不需要的功能糾錯(cuò)流量控制序號(hào)多點(diǎn)線路半雙工或單工鏈路

PPP協(xié)議不需要的功能糾錯(cuò)PPP協(xié)議的組成

1992年制訂了PPP協(xié)議。經(jīng)過1993年和1994年的修訂，現(xiàn)在的PPP協(xié)議已成為因特網(wǎng)的正式標(biāo)準(zhǔn)[RFC1661]。PPP協(xié)議有三個(gè)組成部分

一個(gè)將IP數(shù)據(jù)報(bào)封裝到串行鏈路的方法。鏈路控制協(xié)議LCP(LinkControlProtocol)。網(wǎng)絡(luò)控制協(xié)議NCP(NetworkControlProtocol)。

PPP協(xié)議的組成1992年制訂了PPP協(xié)議。經(jīng)過3.5.2PPP協(xié)議的幀格式標(biāo)志字段F=0x7E（符號(hào)“0x”表示后面的字符是用十六進(jìn)制表示。十六進(jìn)制的7E的二進(jìn)制表示是01111110）。地址字段A只置為0xFF。地址字段實(shí)際上并不起作用。控制字段C通常置為0x03。先發(fā)送IP數(shù)據(jù)報(bào)1211字節(jié)12不超過1500字節(jié)PPP幀7EFF03FACFCSF7E協(xié)議信息部分首部尾部3.5.2PPP協(xié)議的幀格式標(biāo)志字段F=0x7PPP有一個(gè)2個(gè)字節(jié)的協(xié)議字段。當(dāng)協(xié)議字段為0x0021時(shí)，PPP幀的信息字段就是IP數(shù)據(jù)報(bào)。若為0xC021,則信息字段是PPP鏈路控制數(shù)據(jù)。若為0x8021，則表示這是網(wǎng)絡(luò)控制數(shù)據(jù)。

先發(fā)送IP數(shù)據(jù)報(bào)1211字節(jié)12不超過1500字節(jié)PPP幀7EFF03FACFCSF7E協(xié)議信息部分首部尾部PPP有一個(gè)2個(gè)字節(jié)的協(xié)議字段。先發(fā)送IP數(shù)據(jù)報(bào)12透明傳輸問題

當(dāng)PPP用在異步傳輸時(shí)，就使用一種特殊的字符填充法。當(dāng)PPP用在同步傳輸時(shí)，協(xié)議規(guī)定采用硬件來完成比特填充。透明傳輸問題當(dāng)PPP用在異步傳輸時(shí)，就使用一種特殊的字字符填充

將信息字段中出現(xiàn)的每一個(gè)0x7E字節(jié)轉(zhuǎn)變成為2字節(jié)序列(0x7D,0x5E)。若信息字段中出現(xiàn)一個(gè)0x7D的字節(jié),則將其轉(zhuǎn)變成為2字節(jié)序列(0x7D,0x5D)。若信息字段中出現(xiàn)ASCII碼的控制字符（即數(shù)值小于0x20的字符），則在該字符前面要加入一個(gè)0x7D字節(jié)，同時(shí)將該字符的編碼加以改變。

字符填充將信息字段中出現(xiàn)的每一個(gè)0x7E字節(jié)轉(zhuǎn)變成為2零比特填充

在發(fā)送端，只要發(fā)現(xiàn)有5個(gè)連續(xù)1，則立即填入一個(gè)0。接收端對(duì)幀中的比特流進(jìn)行掃描。每當(dāng)發(fā)現(xiàn)5個(gè)連續(xù)1時(shí)，就把這5個(gè)連續(xù)1后的一個(gè)0刪除。

零比特填充01001111101000101001001111110001010010011111010001010信息字段中出現(xiàn)了和標(biāo)志字段F完全一樣的8比特組合發(fā)送端在5個(gè)連1之后填入0比特再發(fā)送出去在接收端把5個(gè)連1之后的0比特刪除會(huì)被誤認(rèn)為是標(biāo)志字段F發(fā)送端填入0比特接收端刪除填入的0比特010011111010001思考：習(xí)題3-18、3-19思考：NCP配置鑒別成功建立失敗失敗通信結(jié)束載波停止檢測(cè)到載波雙方協(xié)商一些選項(xiàng)鑒別網(wǎng)絡(luò)打開終止靜止3.5.3PPP協(xié)議的工作狀態(tài)

使用PPP協(xié)議的狀態(tài)圖NCP配置鑒別成功建立失敗失敗通信載波檢測(cè)到雙方協(xié)商鑒別網(wǎng)3.6HDLC協(xié)議HDLC是一個(gè)在同步網(wǎng)上傳輸數(shù)據(jù)、面向位的數(shù)據(jù)鏈路層協(xié)議，它是由國(guó)際標(biāo)準(zhǔn)化組織（ISO）制