數(shù)據(jù)鏈路層知識(shí)概述課件

數(shù)據(jù)鏈路層

第三章1linwei@數(shù)據(jù)鏈路層第三章1linwei@主要內(nèi)容3.1數(shù)據(jù)鏈路層設(shè)計(jì)要點(diǎn)3.2錯(cuò)誤檢測和糾正3.3基本數(shù)據(jù)鏈路層協(xié)議3.4滑窗協(xié)議3.5協(xié)議驗(yàn)證3.6數(shù)據(jù)鏈路層協(xié)議示例2linwei@主要內(nèi)容3.1數(shù)據(jù)鏈路層設(shè)計(jì)要點(diǎn)2linwei@cuc.e3.1數(shù)據(jù)鏈路層的設(shè)計(jì)要點(diǎn)為網(wǎng)絡(luò)層提供的服務(wù)成幀差錯(cuò)控制流量控制3linwei@3.1數(shù)據(jù)鏈路層的設(shè)計(jì)要點(diǎn)為網(wǎng)絡(luò)層提供的服務(wù)3linwei鏈路層基本功能向網(wǎng)絡(luò)層提供一個(gè)服務(wù)接口處理傳輸錯(cuò)誤調(diào)節(jié)數(shù)據(jù)流（流控）4linwei@鏈路層基本功能向網(wǎng)絡(luò)層提供一個(gè)服務(wù)接口4linwei@cuc分組與幀之間的關(guān)系5linwei@分組與幀之間的關(guān)系5linwei@虛擬通信和實(shí)際通信(a)虛擬通信.(b)實(shí)際通信.6linwei@虛擬通信和實(shí)際通信(a)虛擬通信.6linwei@cuc.數(shù)據(jù)鏈路層提供的服務(wù)無確認(rèn)的無連接服務(wù)用于低誤碼率鏈路或?qū)φ`碼不敏感的業(yè)務(wù).(fiber,utp,real-time)有確認(rèn)的無連接服務(wù)用于高誤碼率鏈路(Wireless)有確認(rèn)的面向連接的服務(wù)保證每個(gè)幀真正接收到且只接收一次。為網(wǎng)絡(luò)層進(jìn)程提供一個(gè)可靠的位流。7linwei@數(shù)據(jù)鏈路層提供的服務(wù)無確認(rèn)的無連接服務(wù)7linwei@cuc例子數(shù)據(jù)鏈路協(xié)議的位置8linwei@例子數(shù)據(jù)鏈路協(xié)議的位置8linwei@

DLL將原始碼流分解為離散的單元，該單元稱為幀。那么接收端如何檢測幀的邊界呢？或者說接收端如何界定幀的開始和結(jié)束呢？討論4種方法：字符計(jì)數(shù)法含字節(jié)填充的分界符法含位填充的分界標(biāo)志法編碼違例

成幀9linwei@DLL將原始碼流分解為離散的單元，該單元字符計(jì)數(shù)法一個(gè)字符流(a)無差錯(cuò).(b)有一個(gè)差錯(cuò).10linwei@字符計(jì)數(shù)法一個(gè)字符流(a)無差錯(cuò).(b)有一個(gè)字符填充(a)有標(biāo)志字節(jié)作為分界的幀.(b)字節(jié)填充前后的4個(gè)字節(jié)序列例子.11linwei@字符填充(a)有標(biāo)志字節(jié)作為分界的幀.11linwei@c比特填充Bit填充，

標(biāo)記01111110(a)原始數(shù)據(jù).(b)線路上的數(shù)據(jù).(c)刪除填充后存儲(chǔ)在接收方存儲(chǔ)器中的數(shù)據(jù).12linwei@比特填充Bit填充，標(biāo)記0111111012linw編碼違例適用于“物理介質(zhì)上的編碼方法中包含冗余信息”的網(wǎng)絡(luò)。例如有些LAN用2個(gè)物理位來編碼1位數(shù)據(jù)?！?”位是“高-低”電平對(duì)，“0”位是“低-高”電平對(duì)。而“高高”“低低”電平對(duì)不用于數(shù)據(jù)，則可用于幀定界。優(yōu)點(diǎn)是沒有額外帶寬開銷13linwei@編碼違例適用于“物理介質(zhì)上的編碼方法中包含冗余信息”的網(wǎng)絡(luò)。為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個(gè)部件。

Acknowledgments,Timers,SequenceNumbersAcknowledgments:當(dāng)接收端正確接收一個(gè)幀，它會(huì)向發(fā)送端返回一個(gè)ACK幀用于指示發(fā)端該幀已正確接收。在某些系統(tǒng)，如果接收的幀不正確，接收端會(huì)發(fā)端返回一個(gè)NACK（NegativeACK）用于指示該幀沒有正確接收.提示發(fā)端不用等待定時(shí)器超時(shí)就立即發(fā)送（重傳）一個(gè)幀.

錯(cuò)誤控制14linwei@為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個(gè)部Timers:

如果沒有定時(shí)器，當(dāng)幀丟失或者

ACK/NACK丟失，會(huì)出現(xiàn)什么情況？定時(shí)器怎么工作呢？當(dāng)發(fā)送一個(gè)幀的時(shí)候，發(fā)端開啟一個(gè)定時(shí)器，當(dāng)在約定的時(shí)間內(nèi)，發(fā)端接收到ACK/NACK，則立即發(fā)送（重發(fā)）一個(gè)幀，且重置定時(shí)器，否則當(dāng)定時(shí)超時(shí)時(shí)，重發(fā)該幀。

SequenceNumbers:

主要解決接收端接收到重復(fù)幀的問題.為了避免接收重復(fù)幀的問題，給發(fā)送的幀分配序列號(hào)，這樣接收端就能夠區(qū)分原始幀和重傳幀。.ErrorControl15linwei@Timers:ErrorControl15linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控是個(gè)動(dòng)態(tài)的過程，取決于負(fù)載強(qiáng)度、接收端緩存大小等，常用的方法：

基于反饋的流控制基于速率的流控制（從來沒有用于DDL）16linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控3.2錯(cuò)誤檢測和糾正糾錯(cuò)碼檢錯(cuò)碼17linwei@3.2錯(cuò)誤檢測和糾正糾錯(cuò)碼17linwei@錯(cuò)誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起的比特錯(cuò)誤通常是突發(fā)性的，而不是獨(dú)立的，單比特錯(cuò)誤，例如：閃電會(huì)引起短暫的突發(fā)比特錯(cuò)誤。18linwei@錯(cuò)誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起糾錯(cuò)碼檢測和糾正數(shù)據(jù)中的錯(cuò)誤

冗余（redundancy）-在數(shù)據(jù)中加入附加的信息。兩種策略：檢錯(cuò)碼:

包含足夠的冗余比特檢錯(cuò)，然后使用NACK告知發(fā)端重傳。糾錯(cuò)碼:包含足夠的冗余比特檢測和糾正錯(cuò)誤。19linwei@糾錯(cuò)碼檢測和糾正數(shù)據(jù)中的錯(cuò)誤19linwei@海明距離給定兩個(gè)碼子，對(duì)其進(jìn)行異或運(yùn)算，然后計(jì)算出異或結(jié)果中1的個(gè)數(shù)，兩個(gè)碼子中不相同的位的個(gè)數(shù)稱為海明距離.

它的意義在于：如果兩個(gè)碼子的海明距離為d，則需要d個(gè)1位錯(cuò)誤才能將一個(gè)碼子轉(zhuǎn)變成另一個(gè)碼子。

20linwei@海明距離給定兩個(gè)碼子，對(duì)其進(jìn)行異或運(yùn)算，然后計(jì)算出異或結(jié)果中

海明距離通常，所有2m

種可能的數(shù)據(jù)報(bào)文都是合法的，但是并非所有的2n（n=m+r；m為數(shù)據(jù)位，r為冗余位）種碼子都被用到。給定計(jì)算校驗(yàn)位的算法后，可以構(gòu)造合法碼子列表，并且可以從該表中找到海明距離最小的兩個(gè)碼子，此距離是整個(gè)編碼方案的海明距離。為了檢測d個(gè)錯(cuò)誤，需要一個(gè)距離為d+1

的編碼方案為了糾正t個(gè)錯(cuò)誤，需要一個(gè)距離為2t+1

的編碼方案21linwei@

海明距離通常，所有2m種可能的數(shù)據(jù)報(bào)文都是合法的，但是奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.1000000(1)1111101(0)奇偶位的海明距離為2，因此它可以檢測單比特錯(cuò)誤，但是不能糾錯(cuò)考慮以下的例子，4個(gè)有效碼子的編碼："0000000000","0000011111","1111100000",and"1111111111".

編碼距離為5,可以糾正2個(gè)錯(cuò)誤。22linwei@奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.22li糾錯(cuò)

設(shè)計(jì)一種編碼方案，每個(gè)碼子有m個(gè)報(bào)文位和r個(gè)校驗(yàn)位，并且能夠糾正所有的單個(gè)錯(cuò)誤。對(duì)于2m

合法報(bào)文，任一個(gè)報(bào)文都對(duì)應(yīng)有n個(gè)非法的碼子，它們與該報(bào)文的距離為1。因此每個(gè)合法的報(bào)文都要求n+1個(gè)位模式供他使用。由于總共有2n個(gè)位模式，所以有(n+1)*2m

<2n,

利用

n=m+r,有：

(m+r+1)<2r，給定m的情況下，這個(gè)條件給出了用于糾正單個(gè)錯(cuò)誤所需要的校驗(yàn)位數(shù)目的下界

例如m=10，r>423linwei@糾錯(cuò)設(shè)計(jì)一種編碼方案，每個(gè)碼子有m檢錯(cuò)碼

糾錯(cuò)碼代價(jià)很大（計(jì)算量和帶寬），因此用在無線通信較為合適，但是在銅線或者光纜，錯(cuò)誤檢測和重傳機(jī)制往往更加有效。

例如，若誤碼是獨(dú)立的，誤碼率為10-6。則對(duì)于1000bit的數(shù)據(jù)塊，需要10個(gè)校驗(yàn)位糾正1個(gè)單bit錯(cuò)誤，1Mbit的需要10Kbit，顯然如果僅僅檢測錯(cuò)誤，每個(gè)數(shù)據(jù)塊1個(gè)奇偶位就足夠了，每一千個(gè)數(shù)據(jù)塊額外傳輸一個(gè)塊，因此開銷小，利用檢錯(cuò)/重傳機(jī)制，則1Mbit只需2001位，相比之下，海明碼需要10000位。

最廣泛使用的檢錯(cuò)碼是多項(xiàng)式編碼，也稱CRC。24linwei@檢錯(cuò)碼

24linwei@CyclicRedundancyCheck基本思想：將位串看成系數(shù)為0或1的多項(xiàng)式。多項(xiàng)式的算術(shù)運(yùn)算以2為模完成，加減法等同于異或，除法為長除運(yùn)算。生成多項(xiàng)式G(x)：事先約定的，最低位，最高位必須是1。校驗(yàn)和：添加到幀序列多項(xiàng)式中，用于檢測傳輸是否有錯(cuò)誤。25linwei@CyclicRedundancyCheck基本思想：將位CyclicRedundancyCheck校驗(yàn)和的計(jì)算方法：(1)假設(shè)G(x)的階為r。在幀的低位端加上r個(gè)0位，所以該幀現(xiàn)在包含m+r位。對(duì)應(yīng)的多項(xiàng)式為xrM(x)。(2)利用模2除法，用對(duì)應(yīng)于G(x)的位串去除xrM(x)的位串。(3)利用模2減法，從對(duì)應(yīng)于xrM(x)的位串中減去余數(shù)，結(jié)果就是將被傳輸?shù)膸ｒ?yàn)和的幀，記為：T(x)。

26linwei@CyclicRedundancyCheck校驗(yàn)和的計(jì)算方CyclicRedundancy

Check校驗(yàn)和的計(jì)算過程27linwei@CyclicRedundancy

Check校驗(yàn)和的計(jì)算CyclicRedundancyCheck分析：1.所有的錯(cuò)誤都能檢測出嗎？

錯(cuò)誤多項(xiàng)式E(x)能被G(x)除盡，則這類錯(cuò)誤無法被檢測。2.所有的一位錯(cuò)誤都將被檢測到。

低階的多項(xiàng)式可以保護(hù)長的幀（K<=i–j,兩個(gè)獨(dú)立的一位錯(cuò)誤）

奇數(shù)項(xiàng)多項(xiàng)式不可能被x+1除盡(奇數(shù)個(gè)位發(fā)生錯(cuò)誤)。帶r個(gè)校驗(yàn)位的多項(xiàng)式編碼可以檢測到所有長度小于等于r的突發(fā)性錯(cuò)誤。28linwei@CyclicRedundancyCheck分析：28liCyclicRedundancyCheck通常用到的3種CRC生成多項(xiàng)式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)

盡管復(fù)雜，可以用硬件構(gòu)造出來29linwei@CyclicRedundancyCheck通常用到的3種3.3基本數(shù)據(jù)鏈路協(xié)議一個(gè)無限制的單工協(xié)議一個(gè)單工的?！葏f(xié)議有噪聲信道的單工協(xié)議30linwei@3.3基本數(shù)據(jù)鏈路協(xié)議一個(gè)無限制的單工協(xié)議30linwei基本數(shù)據(jù)鏈路協(xié)議幾個(gè)假設(shè)：物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層都是獨(dú)立的進(jìn)程，它們通過報(bào)文來相互通信?？煽康摹⒚嫦蜻B接的服務(wù)機(jī)器不會(huì)崩潰31linwei@基本數(shù)據(jù)鏈路協(xié)議幾個(gè)假設(shè)：31linwei@.協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.32linwei@協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.33linwei@協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含無限制的單工協(xié)議假設(shè)條件:數(shù)據(jù)單向傳輸物理信道無誤碼，即無幀損壞或丟失發(fā)/接收端緩存無限大發(fā)端/收端的網(wǎng)絡(luò)層總是處于準(zhǔn)備就緒狀態(tài)34linwei@無限制的單工協(xié)議假設(shè)條件:34linwei@.無限制的

單工協(xié)議35linwei@無限制的

單工協(xié)議35linwei@一個(gè)單工的停/等協(xié)議

假設(shè):不再假設(shè)收端能夠無限快速的處理到來的數(shù)據(jù).基本思想和特點(diǎn)發(fā)端發(fā)送一個(gè)幀，然后等待確認(rèn)(stopandwait.)確認(rèn)幀的內(nèi)容并不重要

數(shù)據(jù)傳輸是單向的，但是必須是雙向鏈路，因此用一個(gè)半雙工的物理信道就足夠了36linwei@一個(gè)單工的停/等協(xié)議

假設(shè):36linwei@單工的等/停協(xié)議37linwei@單工的等/停協(xié)議37linwei@有噪聲信道的單工協(xié)議假設(shè):信道有噪聲，因此可能會(huì)丟/損壞幀簡單的方法:發(fā)端設(shè)置一個(gè)定時(shí)器，如果在規(guī)定的時(shí)間內(nèi)沒有接收到ACK，則重發(fā)該幀.這種方法有沒有問題？38linwei@有噪聲信道的單工協(xié)議假設(shè):38linwei@.有噪聲信道的單工協(xié)議考慮下面的場景：

A傳輸一個(gè)幀

B接收到A傳來的幀A1B產(chǎn)生ACKACK丟失A定時(shí)器超時(shí),重傳B得到A1的副本(將會(huì)把副本送到網(wǎng)絡(luò)層.)(另外一種出現(xiàn)副本的情況是長的時(shí)延)使用序列號(hào)在這個(gè)例子里，1bit就夠了。在協(xié)議中，發(fā)送方在準(zhǔn)備下一個(gè)數(shù)據(jù)項(xiàng)目之前先等待一個(gè)肯定的確認(rèn)，則這樣的協(xié)議稱為（

PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）

39linwei@有噪聲信道的單工協(xié)議考慮下面的場景：

39linwei@cu有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議Continued40linwei@有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議Continu有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議41linwei@有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議41linwe3.4滑窗協(xié)議用于雙向通信使用同一條線路來傳輸兩個(gè)方向上的數(shù)據(jù)反向信道與前向信道有相同的容量.有兩種類型的幀("kind"field):數(shù)據(jù)（Data）ACK(含有最新接收幀的序號(hào)).42linwei@3.4滑窗協(xié)議用于雙向通信42linwei@捎帶確認(rèn)（Piggybacking）Piggybacking–確認(rèn)信息附在往外（反向鏈路）發(fā)送的數(shù)據(jù)幀上的行為。優(yōu)點(diǎn):更好的利用信道帶寬。

問題:為了更好的利用帶寬，數(shù)據(jù)鏈路層應(yīng)該等待下一個(gè)分組多長時(shí)間?43linwei@捎帶確認(rèn)（Piggybacking）Piggybacking滑窗協(xié)議每個(gè)外發(fā)的幀都包含一個(gè)序列號(hào)，其范圍為0~MaxSeq(2n–1).這樣的序列號(hào)正好可以填到一個(gè)n位的域中。等-?；瑒?dòng)窗口協(xié)議使用n=1?；皡f(xié)議的本質(zhì)：在任何時(shí)刻，發(fā)送方總是維持著一組序列號(hào)，分別對(duì)應(yīng)于允許它發(fā)送的幀。稱這些幀落在發(fā)送窗口內(nèi)，接受方也維持一個(gè)接收窗口，對(duì)應(yīng)一組允許他接收的幀。窗口大小可以固定或者不固定。44linwei@滑窗協(xié)議44linwei@滑窗協(xié)議(2)滑窗大小為1，有3個(gè)序列號(hào)的滑動(dòng)窗口(a)初始化(b)第1幀發(fā)送以后(c)第1幀接收以后(d)第一個(gè)確認(rèn)收到后45linwei@滑窗協(xié)議(2)滑窗大小為1，有3個(gè)序列號(hào)的滑動(dòng)窗口45li滑窗協(xié)議1位滑窗協(xié)議GoBackN協(xié)議選擇性重傳協(xié)議46linwei@滑窗協(xié)議1位滑窗協(xié)議46linwei@1位滑窗協(xié)議Continued47linwei@1位滑窗協(xié)議Continued47linwei@cuc.1位滑窗協(xié)議(ctd.)48linwei@1位滑窗協(xié)議(ctd.)48linwei@.1位滑窗協(xié)議(2)針對(duì)協(xié)議4的兩種情況.(a)正常情況.(b)異常情況.

記號(hào)為(seq,ack,packetnumber).星號(hào)表示網(wǎng)絡(luò)層接受一個(gè)分組.49linwei@1位滑窗協(xié)議(2)針對(duì)協(xié)議4的兩種情況.Gobackn協(xié)議

停/等協(xié)議的一個(gè)問題是：往返時(shí)延過長

1000bitframes50kbpschannel，往返傳播時(shí)延500ms(satellite)

發(fā)送1000bit的幀到接收方完全接收需要270ms，520ms后收端才能接收到確認(rèn)（忽略ACK帶來的時(shí)延）。只有4%的有效帶寬被利用，效率很差！

50linwei@Gobackn協(xié)議

50linwei@.管道化利用管道:使得多個(gè)幀可以同時(shí)在一條鏈路上傳輸.性能改善F=framesize(bits)

C=channelcapacity(bps)I=propagationdelayplusprocessorservicetime(seconds)

Timetotransmitasingleframe=F/CTotalDelay=2Ilineutilization=F/(F+2CI)<50%ifF<2CI51linwei@管道化利用管道:51linwei@GoBackN協(xié)議Gobackn–對(duì)用于“接收窗口尺寸為1”的情況如果接收端收到壞幀，則后續(xù)的幀（管道中的）無論正確與否全部丟棄丟棄的幀沒有ACKs.52linwei@GoBackN協(xié)議Gobackn–對(duì)用于“接收窗GoBackN滑窗協(xié)議Continued53linwei@GoBackN滑窗協(xié)議Continued53linwGoBackN滑窗協(xié)議Continued54linwei@GoBackN滑窗協(xié)議Continued54linwGoBackN滑窗協(xié)議Continued55linwei@GoBackN滑窗協(xié)議Continued55linwGoBackN滑窗協(xié)議56linwei@GoBackN滑窗協(xié)議56linwei@.窗口尺寸問題考慮MAX_SEQ=7的場景：發(fā)送方發(fā)送0~7幀.第7幀的捎帶確認(rèn)最終被送回到發(fā)送方.發(fā)送方送出另外8幀，其序號(hào)仍然是0~7現(xiàn)在第7幀的另一個(gè)捎帶確認(rèn)也回來了問題是：屬于第二批的8幀全部成功到達(dá)了嗎？或者是說這8幀全部丟失了（把出錯(cuò)之后丟棄的幀也算作丟失了）？在這兩種情況下，接收方都會(huì)發(fā)送第7幀的確認(rèn)。而發(fā)送方無從分辨。由于這個(gè)原因，未確認(rèn)幀（即窗口大?。┍仨毾拗茷镸AX_SEQ.57linwei@窗口尺寸問題考慮MAX_SEQ=7的場景：57linwGoBackN滑窗協(xié)議用軟件模擬多個(gè)定時(shí)器.58linwei@GoBackN滑窗協(xié)議用軟件模擬多個(gè)定時(shí)器.58linw選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.緩存壞幀以后所有的幀.只對(duì)最后一個(gè)正確接收的幀進(jìn)行確認(rèn)。59linwei@選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.59li選擇性重傳協(xié)議接收側(cè)帶寬與鏈路層緩存之間的折中

這兩種情況下，發(fā)送側(cè)需要緩存，只有接收到ACK后占用的緩存才能釋放。

為了強(qiáng)制執(zhí)行“任何時(shí)候未確認(rèn)幀的個(gè)數(shù)都不應(yīng)該超過Max_Seq”的流控規(guī)則，DLL應(yīng)該能夠enable/disable網(wǎng)絡(luò)層60linwei@選擇性重傳協(xié)議接收側(cè)帶寬與鏈路層緩存之間的折中

60linw使用選擇性重傳的滑動(dòng)窗口協(xié)議Continued61linwei@使用選擇性重傳的滑動(dòng)窗口協(xié)議Continued61linContinued使用選擇性重傳的滑動(dòng)窗口協(xié)議(2)62linwei@Continued使用選擇性重傳的滑動(dòng)窗口協(xié)議(2)62使用選擇性重傳的滑動(dòng)窗口協(xié)議(3)Continued63linwei@使用選擇性重傳的滑動(dòng)窗口協(xié)議(3)Continued63使用選擇性重傳的滑動(dòng)窗口協(xié)議(4)64linwei@使用選擇性重傳的滑動(dòng)窗口協(xié)議(4)64linwei@cuc.非順序接收問題(a)窗口大小為7的初始狀態(tài).(b)7幀都已送出并接收，但是均未被確認(rèn)(c)窗口大小為4的初始狀態(tài)(d)4幀都已送出并接收，但是均未被確認(rèn).65linwei@非順序接收問題(a)窗口大小為7的初始狀態(tài).65linwe數(shù)據(jù)重疊（overlap）問題的本質(zhì)是，當(dāng)接收方向前移動(dòng)窗口后，新的有效序列號(hào)與老的有效序列號(hào)之間有重疊，因此后續(xù)的幀可能是重復(fù)的幀，也有可能是新的幀，但是接收端無法區(qū)分。解決的方法：最大的窗口尺寸應(yīng)該不超過序列號(hào)范圍的一半，即(MAX_SEQ+1)/2.

因此對(duì)3位序列號(hào)，窗口尺寸為466linwei@數(shù)據(jù)重疊（overlap）問題的本質(zhì)是，當(dāng)接收方向前移動(dòng)窗口反向流量輕的問題之前的假設(shè)反向信道負(fù)載較重（因?yàn)椴捎蒙訋Т_認(rèn)）如果反向業(yè)務(wù)輕會(huì)如何？確認(rèn)信息會(huì)滯留很長時(shí)間極端情況，如果在一個(gè)方向上有很大的流量，而另一個(gè)方向上根本沒有流量，則只有MAX_SEQ個(gè)分組被發(fā)出去，協(xié)議就阻塞了。啟用start_ack_timer輔助定時(shí)器，如果定時(shí)器到期前沒有出現(xiàn)反向流量，則發(fā)送一個(gè)單獨(dú)的確認(rèn)幀。67linwei@反向流量輕的問題之前的假設(shè)反向信道負(fù)載較重（因?yàn)椴捎蒙訋Т_認(rèn)3.5協(xié)議驗(yàn)證有限狀態(tài)機(jī)模型Petri網(wǎng)模型68linwei@3.5協(xié)議驗(yàn)證有限狀態(tài)機(jī)模型68linwei@cuc.ed有限狀態(tài)機(jī)模型

協(xié)議規(guī)范和驗(yàn)證:

本節(jié)的目的是學(xué)習(xí)驗(yàn)證協(xié)議的方法狀態(tài)圖對(duì)于驗(yàn)證協(xié)議的正確性和完整性是非常重要的協(xié)議機(jī)；狀態(tài)；轉(zhuǎn)換，死鎖一個(gè)協(xié)議的有限狀態(tài)機(jī)模型可以看作是一個(gè)四元組（S，M，I，T），其中：S是指進(jìn)程和信道可能的狀態(tài)集合M是指能在信道上進(jìn)行交換的幀的集合I是指進(jìn)程的初始狀態(tài)集合T是狀態(tài)之間轉(zhuǎn)換的集合69linwei@有限狀態(tài)機(jī)模型

協(xié)議規(guī)范和驗(yàn)證:

69linwei@cuc.FiniteStateMachinedModels（a）協(xié)議3的狀態(tài)圖(b)轉(zhuǎn)換.70linwei@FiniteStateMachinedModels（aPetri網(wǎng)模型包含兩個(gè)庫所和2個(gè)轉(zhuǎn)換的Petri網(wǎng).庫所，變遷，弧和標(biāo)記71linwei@Petri網(wǎng)模型包含兩個(gè)庫所和2個(gè)轉(zhuǎn)換的Petri網(wǎng).7Petri網(wǎng)模型(2)協(xié)議3的Petri網(wǎng)模型72linwei@Petri網(wǎng)模型(2)協(xié)議3的Petri網(wǎng)模型72li3.6數(shù)據(jù)鏈路層協(xié)議示例HDLC–High-LevelDataLinkControlInternet中的數(shù)據(jù)鏈路層73linwei@3.6數(shù)據(jù)鏈路層協(xié)議示例HDLC–High-LevelHigh-LevelDataLinkControl面向位的協(xié)議的幀格式.74linwei@High-LevelDataLinkControl面向HDLCControlField三種幀的控制域

(a)信息幀

(b)管理幀(c)無序號(hào)幀75linwei@HDLCControlField三種幀的控制域75liHigh-LevelDataLinkControl管理幀類型Type0

是一個(gè)確認(rèn)幀，用于指示下一個(gè)期望的幀。Type1

是一個(gè)否定的確認(rèn)幀，指示一個(gè)傳輸錯(cuò)誤已經(jīng)被檢測到，NEXT域指明了期望被重傳的幀的序列號(hào)。發(fā)送方必須重傳從NEXT開始的所有未被確認(rèn)的幀。Type2

是接收尚未就緒，它確認(rèn)直到Next的所有幀，但是不包含Next幀，告訴發(fā)端不要在發(fā)送了。Type3

是選擇性拒絕。它只要求重傳特定的幀。76linwei@High-LevelDataLinkControl管理

Internet中的數(shù)據(jù)鏈路層Point-to-point線路:路由器之間的租用線路，經(jīng)由modem撥號(hào)登陸主機(jī)的線路

PPP-Point-to-PointProtocol:Standard(RFCs1661-1663)77linwei@

Internet中的數(shù)據(jù)鏈路層Point-to-pointPPP-Point-to-PointProtocol:PPP提供了3類功能:成幀方法，幀格式支持錯(cuò)誤檢測。鏈路控制協(xié)議(LCP)

，可用于啟動(dòng)線路、測試線路、協(xié)商參數(shù)以及當(dāng)線路不再需要的時(shí)候關(guān)閉線路。網(wǎng)絡(luò)控制協(xié)議

：協(xié)商網(wǎng)絡(luò)層選項(xiàng)的方法。與HDLC類似,但是其是面向字符型的.78linwei@PPP-Point-to-PointProtocol:point-to-pointcommunication一臺(tái)家庭個(gè)人計(jì)算機(jī)成為一臺(tái)Internet主機(jī)79linwei@point-to-pointcommunication一臺(tái)PPP–PointtoPointProtocol無序號(hào)模式下PPP的完整的幀格式.80linwei@PPP–PointtoPointProtocol無狀態(tài)機(jī)線路啟動(dòng)到關(guān)閉的狀態(tài)轉(zhuǎn)移圖81linwei@狀態(tài)機(jī)線路啟動(dòng)到關(guān)閉的狀態(tài)轉(zhuǎn)移圖81linwei@cuc.eRFC1661:LCPFrametypesTheLCPframetypes.82linwei@RFC1661:LCPFrametypesTheLC數(shù)據(jù)鏈路層

第三章83linwei@數(shù)據(jù)鏈路層第三章1linwei@主要內(nèi)容3.1數(shù)據(jù)鏈路層設(shè)計(jì)要點(diǎn)3.2錯(cuò)誤檢測和糾正3.3基本數(shù)據(jù)鏈路層協(xié)議3.4滑窗協(xié)議3.5協(xié)議驗(yàn)證3.6數(shù)據(jù)鏈路層協(xié)議示例84linwei@主要內(nèi)容3.1數(shù)據(jù)鏈路層設(shè)計(jì)要點(diǎn)2linwei@cuc.e3.1數(shù)據(jù)鏈路層的設(shè)計(jì)要點(diǎn)為網(wǎng)絡(luò)層提供的服務(wù)成幀差錯(cuò)控制流量控制85linwei@3.1數(shù)據(jù)鏈路層的設(shè)計(jì)要點(diǎn)為網(wǎng)絡(luò)層提供的服務(wù)3linwei鏈路層基本功能向網(wǎng)絡(luò)層提供一個(gè)服務(wù)接口處理傳輸錯(cuò)誤調(diào)節(jié)數(shù)據(jù)流（流控）86linwei@鏈路層基本功能向網(wǎng)絡(luò)層提供一個(gè)服務(wù)接口4linwei@cuc分組與幀之間的關(guān)系87linwei@分組與幀之間的關(guān)系5linwei@虛擬通信和實(shí)際通信(a)虛擬通信.(b)實(shí)際通信.88linwei@虛擬通信和實(shí)際通信(a)虛擬通信.6linwei@cuc.數(shù)據(jù)鏈路層提供的服務(wù)無確認(rèn)的無連接服務(wù)用于低誤碼率鏈路或?qū)φ`碼不敏感的業(yè)務(wù).(fiber,utp,real-time)有確認(rèn)的無連接服務(wù)用于高誤碼率鏈路(Wireless)有確認(rèn)的面向連接的服務(wù)保證每個(gè)幀真正接收到且只接收一次。為網(wǎng)絡(luò)層進(jìn)程提供一個(gè)可靠的位流。89linwei@數(shù)據(jù)鏈路層提供的服務(wù)無確認(rèn)的無連接服務(wù)7linwei@cuc例子數(shù)據(jù)鏈路協(xié)議的位置90linwei@例子數(shù)據(jù)鏈路協(xié)議的位置8linwei@

DLL將原始碼流分解為離散的單元，該單元稱為幀。那么接收端如何檢測幀的邊界呢？或者說接收端如何界定幀的開始和結(jié)束呢？討論4種方法：字符計(jì)數(shù)法含字節(jié)填充的分界符法含位填充的分界標(biāo)志法編碼違例

成幀91linwei@DLL將原始碼流分解為離散的單元，該單元字符計(jì)數(shù)法一個(gè)字符流(a)無差錯(cuò).(b)有一個(gè)差錯(cuò).92linwei@字符計(jì)數(shù)法一個(gè)字符流(a)無差錯(cuò).(b)有一個(gè)字符填充(a)有標(biāo)志字節(jié)作為分界的幀.(b)字節(jié)填充前后的4個(gè)字節(jié)序列例子.93linwei@字符填充(a)有標(biāo)志字節(jié)作為分界的幀.11linwei@c比特填充Bit填充，

標(biāo)記01111110(a)原始數(shù)據(jù).(b)線路上的數(shù)據(jù).(c)刪除填充后存儲(chǔ)在接收方存儲(chǔ)器中的數(shù)據(jù).94linwei@比特填充Bit填充，標(biāo)記0111111012linw編碼違例適用于“物理介質(zhì)上的編碼方法中包含冗余信息”的網(wǎng)絡(luò)。例如有些LAN用2個(gè)物理位來編碼1位數(shù)據(jù)?！?”位是“高-低”電平對(duì)，“0”位是“低-高”電平對(duì)。而“高高”“低低”電平對(duì)不用于數(shù)據(jù)，則可用于幀定界。優(yōu)點(diǎn)是沒有額外帶寬開銷95linwei@編碼違例適用于“物理介質(zhì)上的編碼方法中包含冗余信息”的網(wǎng)絡(luò)。為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個(gè)部件。

Acknowledgments,Timers,SequenceNumbersAcknowledgments:當(dāng)接收端正確接收一個(gè)幀，它會(huì)向發(fā)送端返回一個(gè)ACK幀用于指示發(fā)端該幀已正確接收。在某些系統(tǒng)，如果接收的幀不正確，接收端會(huì)發(fā)端返回一個(gè)NACK（NegativeACK）用于指示該幀沒有正確接收.提示發(fā)端不用等待定時(shí)器超時(shí)就立即發(fā)送（重傳）一個(gè)幀.

錯(cuò)誤控制96linwei@為了保證所有的幀最終傳送到（有可能順序的）目的端，需要三個(gè)部Timers:

如果沒有定時(shí)器，當(dāng)幀丟失或者

ACK/NACK丟失，會(huì)出現(xiàn)什么情況？定時(shí)器怎么工作呢？當(dāng)發(fā)送一個(gè)幀的時(shí)候，發(fā)端開啟一個(gè)定時(shí)器，當(dāng)在約定的時(shí)間內(nèi)，發(fā)端接收到ACK/NACK，則立即發(fā)送（重發(fā)）一個(gè)幀，且重置定時(shí)器，否則當(dāng)定時(shí)超時(shí)時(shí)，重發(fā)該幀。

SequenceNumbers:

主要解決接收端接收到重復(fù)幀的問題.為了避免接收重復(fù)幀的問題，給發(fā)送的幀分配序列號(hào)，這樣接收端就能夠區(qū)分原始幀和重傳幀。.ErrorControl97linwei@Timers:ErrorControl15linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控是個(gè)動(dòng)態(tài)的過程，取決于負(fù)載強(qiáng)度、接收端緩存大小等，常用的方法：

基于反饋的流控制基于速率的流控制（從來沒有用于DDL）98linwei@流控流控主要是處理發(fā)端與接收端之間速率匹配的問題。通常，流控3.2錯(cuò)誤檢測和糾正糾錯(cuò)碼檢錯(cuò)碼99linwei@3.2錯(cuò)誤檢測和糾正糾錯(cuò)碼17linwei@錯(cuò)誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起的比特錯(cuò)誤通常是突發(fā)性的，而不是獨(dú)立的，單比特錯(cuò)誤，例如：閃電會(huì)引起短暫的突發(fā)比特錯(cuò)誤。100linwei@錯(cuò)誤數(shù)據(jù)通信中，鏈路噪聲無處不在，并且研究發(fā)現(xiàn)，鏈路噪聲引起糾錯(cuò)碼檢測和糾正數(shù)據(jù)中的錯(cuò)誤

冗余（redundancy）-在數(shù)據(jù)中加入附加的信息。兩種策略：檢錯(cuò)碼:

包含足夠的冗余比特檢錯(cuò)，然后使用NACK告知發(fā)端重傳。糾錯(cuò)碼:包含足夠的冗余比特檢測和糾正錯(cuò)誤。101linwei@糾錯(cuò)碼檢測和糾正數(shù)據(jù)中的錯(cuò)誤19linwei@海明距離給定兩個(gè)碼子，對(duì)其進(jìn)行異或運(yùn)算，然后計(jì)算出異或結(jié)果中1的個(gè)數(shù)，兩個(gè)碼子中不相同的位的個(gè)數(shù)稱為海明距離.

它的意義在于：如果兩個(gè)碼子的海明距離為d，則需要d個(gè)1位錯(cuò)誤才能將一個(gè)碼子轉(zhuǎn)變成另一個(gè)碼子。

102linwei@海明距離給定兩個(gè)碼子，對(duì)其進(jìn)行異或運(yùn)算，然后計(jì)算出異或結(jié)果中

海明距離通常，所有2m

種可能的數(shù)據(jù)報(bào)文都是合法的，但是并非所有的2n（n=m+r；m為數(shù)據(jù)位，r為冗余位）種碼子都被用到。給定計(jì)算校驗(yàn)位的算法后，可以構(gòu)造合法碼子列表，并且可以從該表中找到海明距離最小的兩個(gè)碼子，此距離是整個(gè)編碼方案的海明距離。為了檢測d個(gè)錯(cuò)誤，需要一個(gè)距離為d+1

的編碼方案為了糾正t個(gè)錯(cuò)誤，需要一個(gè)距離為2t+1

的編碼方案103linwei@

海明距離通常，所有2m種可能的數(shù)據(jù)報(bào)文都是合法的，但是奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.1000000(1)1111101(0)奇偶位的海明距離為2，因此它可以檢測單比特錯(cuò)誤，但是不能糾錯(cuò)考慮以下的例子，4個(gè)有效碼子的編碼："0000000000","0000011111","1111100000",and"1111111111".

編碼距離為5,可以糾正2個(gè)錯(cuò)誤。104linwei@奇偶位保證碼子中“1”位的數(shù)目是偶數(shù)（或者奇數(shù)）。.22li糾錯(cuò)

設(shè)計(jì)一種編碼方案，每個(gè)碼子有m個(gè)報(bào)文位和r個(gè)校驗(yàn)位，并且能夠糾正所有的單個(gè)錯(cuò)誤。對(duì)于2m

合法報(bào)文，任一個(gè)報(bào)文都對(duì)應(yīng)有n個(gè)非法的碼子，它們與該報(bào)文的距離為1。因此每個(gè)合法的報(bào)文都要求n+1個(gè)位模式供他使用。由于總共有2n個(gè)位模式，所以有(n+1)*2m

<2n,

利用

n=m+r,有：

(m+r+1)<2r，給定m的情況下，這個(gè)條件給出了用于糾正單個(gè)錯(cuò)誤所需要的校驗(yàn)位數(shù)目的下界

例如m=10，r>4105linwei@糾錯(cuò)設(shè)計(jì)一種編碼方案，每個(gè)碼子有m檢錯(cuò)碼

糾錯(cuò)碼代價(jià)很大（計(jì)算量和帶寬），因此用在無線通信較為合適，但是在銅線或者光纜，錯(cuò)誤檢測和重傳機(jī)制往往更加有效。

例如，若誤碼是獨(dú)立的，誤碼率為10-6。則對(duì)于1000bit的數(shù)據(jù)塊，需要10個(gè)校驗(yàn)位糾正1個(gè)單bit錯(cuò)誤，1Mbit的需要10Kbit，顯然如果僅僅檢測錯(cuò)誤，每個(gè)數(shù)據(jù)塊1個(gè)奇偶位就足夠了，每一千個(gè)數(shù)據(jù)塊額外傳輸一個(gè)塊，因此開銷小，利用檢錯(cuò)/重傳機(jī)制，則1Mbit只需2001位，相比之下，海明碼需要10000位。

最廣泛使用的檢錯(cuò)碼是多項(xiàng)式編碼，也稱CRC。106linwei@檢錯(cuò)碼

24linwei@CyclicRedundancyCheck基本思想：將位串看成系數(shù)為0或1的多項(xiàng)式。多項(xiàng)式的算術(shù)運(yùn)算以2為模完成，加減法等同于異或，除法為長除運(yùn)算。生成多項(xiàng)式G(x)：事先約定的，最低位，最高位必須是1。校驗(yàn)和：添加到幀序列多項(xiàng)式中，用于檢測傳輸是否有錯(cuò)誤。107linwei@CyclicRedundancyCheck基本思想：將位CyclicRedundancyCheck校驗(yàn)和的計(jì)算方法：(1)假設(shè)G(x)的階為r。在幀的低位端加上r個(gè)0位，所以該幀現(xiàn)在包含m+r位。對(duì)應(yīng)的多項(xiàng)式為xrM(x)。(2)利用模2除法，用對(duì)應(yīng)于G(x)的位串去除xrM(x)的位串。(3)利用模2減法，從對(duì)應(yīng)于xrM(x)的位串中減去余數(shù)，結(jié)果就是將被傳輸?shù)膸ｒ?yàn)和的幀，記為：T(x)。

108linwei@CyclicRedundancyCheck校驗(yàn)和的計(jì)算方CyclicRedundancy

Check校驗(yàn)和的計(jì)算過程109linwei@CyclicRedundancy

Check校驗(yàn)和的計(jì)算CyclicRedundancyCheck分析：1.所有的錯(cuò)誤都能檢測出嗎？

錯(cuò)誤多項(xiàng)式E(x)能被G(x)除盡，則這類錯(cuò)誤無法被檢測。2.所有的一位錯(cuò)誤都將被檢測到。

低階的多項(xiàng)式可以保護(hù)長的幀（K<=i–j,兩個(gè)獨(dú)立的一位錯(cuò)誤）

奇數(shù)項(xiàng)多項(xiàng)式不可能被x+1除盡(奇數(shù)個(gè)位發(fā)生錯(cuò)誤)。帶r個(gè)校驗(yàn)位的多項(xiàng)式編碼可以檢測到所有長度小于等于r的突發(fā)性錯(cuò)誤。110linwei@CyclicRedundancyCheck分析：28liCyclicRedundancyCheck通常用到的3種CRC生成多項(xiàng)式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)

盡管復(fù)雜，可以用硬件構(gòu)造出來111linwei@CyclicRedundancyCheck通常用到的3種3.3基本數(shù)據(jù)鏈路協(xié)議一個(gè)無限制的單工協(xié)議一個(gè)單工的?！葏f(xié)議有噪聲信道的單工協(xié)議112linwei@3.3基本數(shù)據(jù)鏈路協(xié)議一個(gè)無限制的單工協(xié)議30linwei基本數(shù)據(jù)鏈路協(xié)議幾個(gè)假設(shè)：物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層都是獨(dú)立的進(jìn)程，它們通過報(bào)文來相互通信?？煽康?、面向連接的服務(wù)機(jī)器不會(huì)崩潰113linwei@基本數(shù)據(jù)鏈路協(xié)議幾個(gè)假設(shè)：31linwei@.協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.114linwei@協(xié)議定義Continued協(xié)議中需要用到的一些定義。這些協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含在頭文件protocol.h中.115linwei@協(xié)議定義

(ctd.)協(xié)議中需要用到的一些定義。這些定義包含無限制的單工協(xié)議假設(shè)條件:數(shù)據(jù)單向傳輸物理信道無誤碼，即無幀損壞或丟失發(fā)/接收端緩存無限大發(fā)端/收端的網(wǎng)絡(luò)層總是處于準(zhǔn)備就緒狀態(tài)116linwei@無限制的單工協(xié)議假設(shè)條件:34linwei@.無限制的

單工協(xié)議117linwei@無限制的

單工協(xié)議35linwei@一個(gè)單工的停/等協(xié)議

假設(shè):不再假設(shè)收端能夠無限快速的處理到來的數(shù)據(jù).基本思想和特點(diǎn)發(fā)端發(fā)送一個(gè)幀，然后等待確認(rèn)(stopandwait.)確認(rèn)幀的內(nèi)容并不重要

數(shù)據(jù)傳輸是單向的，但是必須是雙向鏈路，因此用一個(gè)半雙工的物理信道就足夠了118linwei@一個(gè)單工的停/等協(xié)議

假設(shè):36linwei@單工的等/停協(xié)議119linwei@單工的等/停協(xié)議37linwei@有噪聲信道的單工協(xié)議假設(shè):信道有噪聲，因此可能會(huì)丟/損壞幀簡單的方法:發(fā)端設(shè)置一個(gè)定時(shí)器，如果在規(guī)定的時(shí)間內(nèi)沒有接收到ACK，則重發(fā)該幀.這種方法有沒有問題？120linwei@有噪聲信道的單工協(xié)議假設(shè):38linwei@.有噪聲信道的單工協(xié)議考慮下面的場景：

A傳輸一個(gè)幀

B接收到A傳來的幀A1B產(chǎn)生ACKACK丟失A定時(shí)器超時(shí),重傳B得到A1的副本(將會(huì)把副本送到網(wǎng)絡(luò)層.)(另外一種出現(xiàn)副本的情況是長的時(shí)延)使用序列號(hào)在這個(gè)例子里，1bit就夠了。在協(xié)議中，發(fā)送方在準(zhǔn)備下一個(gè)數(shù)據(jù)項(xiàng)目之前先等待一個(gè)肯定的確認(rèn)，則這樣的協(xié)議稱為（

PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）

121linwei@有噪聲信道的單工協(xié)議考慮下面的場景：

39linwei@cu有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議Continued122linwei@有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議Continu有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議123linwei@有噪聲信道的單工協(xié)議一個(gè)支持重傳的肯定確認(rèn)協(xié)議41linwe3.4滑窗協(xié)議用于雙向通信使用同一條線路來傳輸兩個(gè)方向上的數(shù)據(jù)反向信道與前向信道有相同的容量.有兩種類型的幀("kind"field):數(shù)據(jù)（Data）ACK(含有最新接收幀的序號(hào)).124linwei@3.4滑窗協(xié)議用于雙向通信42linwei@捎帶確認(rèn)（Piggybacking）Piggybacking–確認(rèn)信息附在往外（反向鏈路）發(fā)送的數(shù)據(jù)幀上的行為。優(yōu)點(diǎn):更好的利用信道帶寬。

問題:為了更好的利用帶寬，數(shù)據(jù)鏈路層應(yīng)該等待下一個(gè)分組多長時(shí)間?125linwei@捎帶確認(rèn)（Piggybacking）Piggybacking滑窗協(xié)議每個(gè)外發(fā)的幀都包含一個(gè)序列號(hào)，其范圍為0~MaxSeq(2n–1).這樣的序列號(hào)正好可以填到一個(gè)n位的域中。等-?；瑒?dòng)窗口協(xié)議使用n=1?；皡f(xié)議的本質(zhì)：在任何時(shí)刻，發(fā)送方總是維持著一組序列號(hào)，分別對(duì)應(yīng)于允許它發(fā)送的幀。稱這些幀落在發(fā)送窗口內(nèi)，接受方也維持一個(gè)接收窗口，對(duì)應(yīng)一組允許他接收的幀。窗口大小可以固定或者不固定。126linwei@滑窗協(xié)議44linwei@滑窗協(xié)議(2)滑窗大小為1，有3個(gè)序列號(hào)的滑動(dòng)窗口(a)初始化(b)第1幀發(fā)送以后(c)第1幀接收以后(d)第一個(gè)確認(rèn)收到后127linwei@滑窗協(xié)議(2)滑窗大小為1，有3個(gè)序列號(hào)的滑動(dòng)窗口45li滑窗協(xié)議1位滑窗協(xié)議GoBackN協(xié)議選擇性重傳協(xié)議128linwei@滑窗協(xié)議1位滑窗協(xié)議46linwei@1位滑窗協(xié)議Continued129linwei@1位滑窗協(xié)議Continued47linwei@cuc.1位滑窗協(xié)議(ctd.)130linwei@1位滑窗協(xié)議(ctd.)48linwei@.1位滑窗協(xié)議(2)針對(duì)協(xié)議4的兩種情況.(a)正常情況.(b)異常情況.

記號(hào)為(seq,ack,packetnumber).星號(hào)表示網(wǎng)絡(luò)層接受一個(gè)分組.131linwei@1位滑窗協(xié)議(2)針對(duì)協(xié)議4的兩種情況.Gobackn協(xié)議

停/等協(xié)議的一個(gè)問題是：往返時(shí)延過長

1000bitframes50kbpschannel，往返傳播時(shí)延500ms(satellite)

發(fā)送1000bit的幀到接收方完全接收需要270ms，520ms后收端才能接收到確認(rèn)（忽略ACK帶來的時(shí)延）。只有4%的有效帶寬被利用，效率很差！

132linwei@Gobackn協(xié)議

50linwei@.管道化利用管道:使得多個(gè)幀可以同時(shí)在一條鏈路上傳輸.性能改善F=framesize(bits)

C=channelcapacity(bps)I=propagationdelayplusprocessorservicetime(seconds)

Timetotransmitasingleframe=F/CTotalDelay=2Ilineutilization=F/(F+2CI)<50%ifF<2CI133linwei@管道化利用管道:51linwei@GoBackN協(xié)議Gobackn–對(duì)用于“接收窗口尺寸為1”的情況如果接收端收到壞幀，則后續(xù)的幀（管道中的）無論正確與否全部丟棄丟棄的幀沒有ACKs.134linwei@GoBackN協(xié)議Gobackn–對(duì)用于“接收窗GoBackN滑窗協(xié)議Continued135linwei@GoBackN滑窗協(xié)議Continued53linwGoBackN滑窗協(xié)議Continued136linwei@GoBackN滑窗協(xié)議Continued54linwGoBackN滑窗協(xié)議Continued137linwei@GoBackN滑窗協(xié)議Continued55linwGoBackN滑窗協(xié)議138linwei@GoBackN滑窗協(xié)議56linwei@.窗口尺寸問題考慮MAX_SEQ=7的場景：發(fā)送方發(fā)送0~7幀.第7幀的捎帶確認(rèn)最終被送回到發(fā)送方.發(fā)送方送出另外8幀，其序號(hào)仍然是0~7現(xiàn)在第7幀的另一個(gè)捎帶確認(rèn)也回來了問題是：屬于第二批的8幀全部成功到達(dá)了嗎？或者是說這8幀全部丟失了（把出錯(cuò)之后丟棄的幀也算作丟失了）？在這兩種情況下，接收方都會(huì)發(fā)送第7幀的確認(rèn)。而發(fā)送方無從分辨。由于這個(gè)原因，未確認(rèn)幀（即窗口大?。┍仨毾拗茷镸AX_SEQ.139linwei@窗口尺寸問題考慮MAX_SEQ=7的場景：57linwGoBackN滑窗協(xié)議用軟件模擬多個(gè)定時(shí)器.140linwei@GoBackN滑窗協(xié)議用軟件模擬多個(gè)定時(shí)器.58linw選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.緩存壞幀以后所有的幀.只對(duì)最后一個(gè)正確接收的幀進(jìn)行確認(rèn)。141linwei@選擇性重傳協(xié)議選擇性重傳–接收窗口尺寸大于1.59li選擇性重傳協(xié)議接收側(cè)帶寬與鏈路層緩存之間的折中

這兩種情況下，發(fā)送側(cè)需要緩存，只有接收到ACK后占用的緩存才能釋放。

為了強(qiáng)制執(zhí)行“任何時(shí)候未確認(rèn)幀的個(gè)數(shù)都不應(yīng)該超過Max_Seq”的流控規(guī)則，DLL應(yīng)該能夠enable/disable網(wǎng)絡(luò)層142linwei@選擇性重傳協(xié)議接收側(cè)帶寬與鏈路層緩存之間的折中

60linw使用選擇性重傳的滑動(dòng)窗口協(xié)議Continued143linwei@使用選擇性重傳的滑動(dòng)窗口協(xié)議Continued61linContinued使用選擇性重傳的滑動(dòng)窗口協(xié)議(2)144linwei@Continued使用選擇性重傳的滑動(dòng)窗口協(xié)議(2)62使用選擇性重傳的滑動(dòng)窗口協(xié)議(3)Continued145linwei@使用選擇性重傳的滑動(dòng)窗口協(xié)議(3)Continued63使用選擇性重傳的滑動(dòng)窗口協(xié)議(4)146linwei@使用選擇性重傳的滑動(dòng)窗口協(xié)議(4)64linwei@cuc.非順序接收問題(a)窗口大小為7的初始狀態(tài).(b)7幀都已送出并接收，但是均未被確認(rèn)(c)窗口大小為4的初始狀態(tài)(d)4幀都已送出并接收，但是均未被確認(rèn).147linwei@非順序接