復旦本科第3章+數據鏈路層課件

1第三章數據鏈路層曹袖（xiucao@）2015.10第三章數據鏈路層2數據鏈路層的功能（3.1）幀同步機制差錯檢測與校正（3.2）簡單差錯控制編碼：奇偶校驗碼、Internet檢驗和、循環(huán)冗余碼(CRC)、線性分組碼卷積碼RS碼數據鏈路協(xié)議（3.3）停等協(xié)議滑動窗口協(xié)議數據鏈路層協(xié)議舉例（3.4）HDLCPPP數據鏈路層的功能3

數據鏈路層的基本功能是在物理層提供的比特流傳輸服務基礎上，把服務用戶（網絡層）來的數據沿一段邏輯鏈路可靠地傳遞給相鄰的節(jié)點網絡層。涉及4方面的內容：幀同步：約定處理的基本單元（幀，或稱DL-PDU），進行幀的起始和結束定位。傳輸過程中可能有差錯、流量等需要處理和控制。更有效地利用鏈路。差錯控制（可靠傳遞）差錯檢測與校正。反饋重發(fā)：確認和重傳。超時和序號：一幀可能完全消失，或重復。幀同步機制5有2類通信協(xié)議（同步）機制：

異步協(xié)議（字符為單位同步，字符間異步：字符內連續(xù)傳輸）在字符起始處進行同步位同步：發(fā)送方和接收方采用近似同一頻率的時鐘，短時間內時鐘的偏移是可以忍受的。同步協(xié)議（幀為單位同步，字符間同步：幀內連續(xù)傳輸）在幀（比較大的數據單元）的起始處同步。維持固定的時鐘，采用某種方法（比如上章介紹的4B/5B編碼等）將時鐘信號編碼進數據中。面向字符的同步協(xié)議：特殊字符表示幀的開始和結束。面向比特的同步協(xié)議：特殊比特模式表示幀的開始和結束。字節(jié)計數的同步協(xié)議：特殊字符表示開始，字節(jié)數表示結束。違例編碼法：采用不在正常數據部分出現(xiàn)的物理信號模式。固定長度（SONET/ATM/T1）：搜索特定比特模式來確定開始。起止式異步規(guī)程

起始位和終止位進行同步，起始位為低電平，終止位和空閑位為高電平。

接收端通過檢測起始位的下降前沿來決定字符的開始，并作為后面各位的定時基準。大部分接收端采用更短周期時鐘：比如16倍時鐘。簡單、信道有效利用率低、差錯和通信控制能力差。如：1個起始位、5~8個數據位、0~1個奇/偶校驗位、1~2個終止位6面向字符的同步協(xié)議

利用一些特殊定義的字符來標識幀的起始位置，分隔不同的段，控制信息交換的過程。字符填充：特殊字符可能在數據部分出現(xiàn)。一種方案：利用轉義字符DLE(Data

Link

Escape)來實現(xiàn)數據透明在控制字符前面有一個DLE時才具有特殊意義。每個獨立的控制字符作為普通的數據字符。

若數據段本身出現(xiàn)DLE，則在前面插入一個DLE。接收方接收到連續(xù)兩個DLE，則去掉第一個DLE，并且作為普通字符看待，不再具有轉義意義。例：接收到DLE/DLE/DLE/ETX

表示DLE(data)

+

ETX(control)特殊字符隨采用的字符編碼集而不同（ASCII/EBCDIC）。有很大局限性（早期使用較多）。ISO

1745Q:來自網絡層的分組放在哪？7面向比特的同步規(guī)程

通過一個特定的比特模式“01111110”來標識幀的起始位置。比特填充：保證數據部分不會出現(xiàn)連續(xù)6個1幀中的其他字段中如果出現(xiàn)連續(xù)5個1，則之后插入一個0。當接收時，如果出現(xiàn)連續(xù)5個1后跟一個0，則刪除0。HDLC相比面向字符，兼容性好，硬件實現(xiàn)方便。8字節(jié)計數的同步規(guī)程同步字符來進行幀同步，SOH標志幀開始。字節(jié)計數來確定幀的結束邊界位置。CRC1對前面標題部分校驗，CRC2對數據部分校驗。–特殊字符少，但Count的差錯可能是災難性的。違例編碼法通過不會在數據部分出現(xiàn)的編碼信號來進行定位。比如曼徹斯特編碼中的高-高/低-低信號。字節(jié)計數的同步規(guī)程/違例編碼法9固定長度

SONET幀固定為810字節(jié)，每行前面三個字節(jié)頭部，87字節(jié)用戶數據，每幀的前面兩個字節(jié)包含一個特殊的比特模式來表示幀的開始。數據部分沒有進行填充來保證數據透明。

接收方首先檢查相應的幀開始模式，然后檢查每隔810字節(jié)后是否也是相同的比特模式，如果不是，則重新掃描幀開始模式。10固定長度+HEC

ATM（異步傳輸模式）采用53字節(jié)的信元cell，其中5個字節(jié)的頭部中最后一個字節(jié)為HEC（信頭差錯校正）。同步狀態(tài)：搜索逐比特檢查HEC預同步同步逐信元檢查HEC連續(xù)

次HEC正確HEC正確HEC不正確連續(xù)

次HEC不正確11差錯檢測與校正：傳輸差錯特性鏈路上有兩種不同的差錯隨機差錯：隨機熱噪聲隨機熱噪聲是信道固有的、持續(xù)存在的；碼元（比特）的差錯是獨立的，和前后的碼元無關；隨機錯的概率很低，物理信道的設計保證相當大的信噪比。誤碼率(BER)：突發(fā)差錯：沖擊噪聲外界的因素，持續(xù)時間短，突發(fā)性；傳輸中產生差錯的主要原因；突發(fā)長度：突發(fā)差錯發(fā)生的第一個碼元到有錯的最后一個碼元間所有碼元的個數。比如4800bps信道上的10ms的沖擊噪聲的突發(fā)長度為48比特。12差錯控制通常通過差錯編碼來實現(xiàn)。

基本思想：在被傳送的信息中附加一些監(jiān)督位（碼元），在收和發(fā)之間建立某種校驗關系，當這種校驗關系因傳輸錯誤而受到破壞時，可以被發(fā)現(xiàn)甚至糾正錯誤，這種檢錯與糾錯能力是用信息量的冗余度來換取的。

差錯編碼：對要發(fā)送的信息位(k)附加上按照某種數學關系產生的冗余/監(jiān)督位(r)。編碼效率R=k/(k+r)：碼字中信息位所占的比例。漏檢率：接收者無法了解到信息位出錯的概率。按照：是否能糾錯：檢錯碼和糾錯碼。信息碼元和冗余碼元之間的關系是否為線性：線性碼和非線性碼。信息碼元和冗余碼元之間的約束方式：分組碼和卷積碼。糾正錯誤類型：糾正隨機錯誤和糾正突發(fā)錯誤碼。

差錯編碼的任務就是要根據不同的差錯特性，設計出編碼效率高、糾錯能力強的編碼。實現(xiàn)中，根據需要盡量簡化編碼實現(xiàn)的復雜度，節(jié)省設計費用。13差錯控制編碼一些差錯編碼術語14

碼元：數據通信中每一個符號的通稱。在差錯編碼中一般用二進制表示，此時對應于比特（位）。碼字：若干個碼元序列組成的數據單元。碼長：碼字中碼元的數目。碼重：碼字中非0數字的數目對于二進制碼來講，碼重W就是碼字中1的數目。例如碼字10100，碼長n=5，碼重W=2。

碼距（漢明/海明距離）：兩個等長碼字之間對應符號不同的數目

對于二進制碼字而言，兩個碼字之間的模二相加，其不同的對應位必為1，相同的對應位必為0。兩個碼字之間模二相加得到的碼重就是這兩個碼字之間的距離。如：碼字10100與11000之間的碼距d=2。

最小碼距：在碼字集合中全體碼字之間距離的最小數值，表示為dmin。差錯控制方式自動請求重發(fā)ARQ（Automatic

Request

for

Repeat）接收方檢測錯誤，通知發(fā)送方重傳。雙向信道，發(fā)送方緩存發(fā)送的數據。前向糾錯FEC（Forward

ErrorCorrection）接收方不僅可以檢測錯誤，而且知道錯誤的位置、加以糾正。采用糾錯碼，無需反向信道，無需重發(fā)。

糾錯碼一般說來要比檢錯碼使用更多的冗余位，也就是說編碼效率低，而且糾錯的設備也比檢錯的設備復雜得多混合糾錯HEC（Hybrid

Error

Correction）：ARQ和FEC結合誤碼率較高時采用ARQ，低時采用FEC。（簡單的FEC，不行則ARQ）15奇偶校驗水平(橫向)奇偶校驗垂直(縱向)奇偶校驗

檢測出每列（段）中所有奇數（1、3…）個錯；突發(fā)錯誤的漏檢率為50%；在發(fā)送和接收的過程中進行編解碼。各段同一位上的奇數個錯；長度小于等于p的突發(fā)差錯；

編碼和檢測相比垂直校驗而言實現(xiàn)要復雜一些。16Internet校驗和18高層協(xié)議的軟件校驗方法。

每2個字節(jié)為一組(word)，按照二進制反碼運算相加。–最后如果為單字節(jié)，則附加一個為0的字節(jié)。生成校驗和

校驗和字段為0，然后二進制反碼相加，最后取其反碼作為校驗和的取值。驗證校驗和

按照二進制反碼運算相加，如果為全1（-0），則說明校驗和正確。u_short

cksum(u_short

*buf,

int

count{register

u_long

sum

=

0;while

(count--){sum

+=

*buf++;if

(sum

&

0xFFFF0000){/*

carry

occurred,so

wrap

around

*/sum

&=

0xFFFF;sum++;}}return

?(sum

&

0xFFFF);}RFC1071/wiki/Cyclic_redundancy_check計算機網絡/存儲中使用廣泛的檢錯碼糾錯碼的編碼效率較低，常采用檢錯碼＋ARQ。也稱為多項式碼二進制比特串和一個只有0和1兩個系數的多項式一一對應；k位信息位對應于一個(k-1)次多項式K(x):比如1011011；r位冗余位對應于一個(r-1)次多項式R(x):比如110110；信息位＋冗余位（n=k+r）對應于一個(n-1)次多項式 T(x)=xrK(x)+R(x)編碼：找一個生成多項式G(x)（r次多項式，最高位的系數為1），

xrK(x)除以G(x)得到的余式為冗余位R(x)。解碼：接收方的碼字除以G(x)，如余式為0（能整除）表示無錯。19循環(huán)冗余碼CRC循環(huán)冗余碼CRC（續(xù)）CRC的多項式運算采用模2運算（異或、按位加/減）半加

半減＝–例：信息位1010001，多項式K(x)=x6+x4+1；生成多項式G(x)=x4+x2+x+1（對應代碼10111）；則r=4，那么：20….即：R(x)=x3+x2+1循環(huán)冗余碼CRC（續(xù)）

差錯模式（差錯多項式）E(x)＝發(fā)送碼字和接收碼字的半加，其中1的位置對應變化信息位（差錯）的位置。若E(x)能被G(x)整除，則CRC不能檢測這樣的錯誤。Q:T(x)+E(x)是什么？21生成多項式若r次多項式G(x)含(x+1)的因子，則能檢測出所有奇數位錯：

若G(x)中不含x的因子，即G(x)中的常數項為1，則能檢測出所有突發(fā)長度 r的突發(fā)錯：n-1，除不盡xe+1，則

若G(x)中不含x的因子，且對任何0<e能檢測出所有的雙錯：22生成多項式（續(xù)）

若G(x)中不含x的因子，則對突發(fā)長度為r+1的突發(fā)錯誤的漏檢率為2-(r-1)

。

若G(x)中不含x的因子，則對突發(fā)長度b(b>r+1)的突發(fā)錯誤的漏檢率為2-r

。23生成多項式（續(xù)）若適當選取r次多項式G(x)，滿足：含有x+1因子。常數項不為0：不含x的因子。周期大于等于n·

周期e為使G(x)能除盡xe+1的最小正整數。則能：檢測出所有奇數位錯、突發(fā)長度小于等于r的突發(fā)錯、雙錯。

突發(fā)長度為r+1的突發(fā)錯誤的漏檢率為2-(r-1)，對突發(fā)長度b(b>r+1)的突發(fā)錯誤的漏檢率為2-r

。常用的CRC多項式：IBM

BSC/USB802.15.4/CDMA/Bluetooth/HDLC/PPPEthernet/MPEG/PNG24碼字輸出端輸出開關信息輸入端CRC硬件實現(xiàn)R0R1Rr-1g1g2gr-1K(x)=1010001T(x)=1010001110125例

除以G(x)的運算可以通過移位寄存器和半加器來實現(xiàn)：

軟件實現(xiàn)：查表線性分組碼26

線性：信息碼元與監(jiān)督碼元之間的關系可以用一組線性方程來表示。

分組：將信息碼元若干位為一組，該組監(jiān)督碼元僅與本組信息位有關。線性分組碼的線性特性任意兩個許用碼字的和也是許用碼字。碼集（碼字集合）的最小碼距等于非零碼的最小碼重。一些線性分組碼奇偶校驗循環(huán)冗余碼海明碼Reed-Solomon碼碼集漢明(海明)距離和檢/糾錯能力27假設要傳送的消息為A/B兩個狀態(tài)編碼（碼字）–

A:

0 B:

1海明距離=1；沒有檢錯/糾錯。–

A:

00 B:

11海明距離=2；{01,10}不用，可以檢測1比特錯，沒有糾錯能力。–

A:

000 B:

111海明距離=3；檢測出兩位及兩位以下差錯；糾正1比特差錯。碼集海明距離和檢/糾錯能力（續(xù)）28為檢出e個錯碼，要求碼集的海明距離d≥e+1。為糾正t個錯碼，要求碼集的海明距離d≥2t+1。為檢出e個錯碼，同時能糾正t個錯碼，則應滿足

d≥e+t+1

(e>t)。例：if

e=2,

t=1,

then

d≥e+t+1=4–{0000,1111} d=4,能檢2個錯碼，能糾1個錯碼；–{0011,0101,0110},{1001,1010,1100} 能檢1個錯碼；–{1100,1011} 能糾1位錯。糾正一比特錯的線性分組碼：海明碼回顧奇偶校驗：一個k=n-1的信息位an-1an-2

…a1加上一個偶校驗位a0（an-1an-2

…a1a0）。接收端：利用一個監(jiān)督關系式計算校正因子S（=0和1），分別區(qū)分無錯和有錯（奇數位錯）的情況：

擴展（Hamming碼）：k位信息位后增加r個冗余位構成n(=k+r)位的碼字。每個冗余位是通過信息位中的某些位半加后的結果。對應的接收方通過r個監(jiān)督關系式產生r個校正因子來區(qū)分無錯和n位的碼字中一位錯。要求：29Hamming

codes

with

additional

parity

(SECDED)Hamming

codes

have

a

minimumdistance

of

3,

whichmeans

that

the

code

can

detect

and

correct

a

single

error,

but

a

double

bit

error

isindistinguishable

froma

different

code

with

a

single

bit

error.

Thus,

they

can

detect

double-bit

errors

onlyif

correction

is

not

attempted.By

including

an

extra

parity

bit,

it

is

possible

to

increase

the

minimumdistance

of

the

Hamming

code

to

4.

This

gives

the

code

the

ability

to

detectand

correct

a

single

error

and

at

the

same

time

detect

(but

not

correct)

a

double

error.

(Itcould

also

be

used

to

detect

up

to3

errors

but

notcorrect

any.)This

code

system

is

popular

in

computer

memory

systems,

where

it

is

known

as

SECDED

("single

error

correction,

double

error

detection").Particularly

popular

is

the

(72,64)

code,

atruncated

(127,120)

Hamming

code

plus

an

additional

parity

bit,

which

has

the

same

space

overheadas

a

(9,8)

parity

code.an

overall

parity

bit

(bit

0)is

included,

the

code

can

detect

(but

not

correct)

any

two-bit

error,

making

a

SECDED

code.

The

overall

parityindicates

whether

the

total

numberof

errors

is

even

orodd.

If

the

basic

Hamming

code

detects

an

error,

but

the

overall

parity

says

that

there

arean

even

number

of

errors,

an

uncorrectable

2-bit

error

has

occurred.海明碼（續(xù)）：例子

假設信息位為k=4，則r 3。取r=3，n=7，即a6a5a4a3

+a2a1a0。（編碼效率R=4/7）冗余位a2、a1和a0是信息位中的某幾位半加得到。三個監(jiān)督關系式和校正因子S2S1S0來自冗余位a2a1a0與信息位a6a5a4a3半加S2S1S0區(qū)分無錯和7位碼字中某一位有錯（糾錯）的情況S2

S1

S0000001010100011101110111錯碼位置無錯a0a1a2a3a4a5a6海明距離為3 糾正單比特差錯或檢測出2個比特差錯,對于(7,4)海明碼兩者同時滿足。

實踐中進一步增加了一個奇偶校驗位，使得海明距離為4（如果檢測出差錯，但奇偶校驗為偶數個差錯，說明為2個比特差錯，否則為單比特差錯）。30海明碼（續(xù)）：糾錯性能

信息位越長，編碼效率越高。如：k=7，冗余位最少為4，編碼效率為7/11。（k→∞，編碼效率k/(k+r)趨于100％）糾正突發(fā)錯誤–連續(xù)P個碼字排成一個矩陣，每行一個碼字，從而可以糾正突發(fā)長度 P的突發(fā)錯。31RS（Reed-Solomon）碼*：伽羅瓦域32伽羅瓦域（有限域）：GF(pm)有限域的階（有限域中元素的個數）一定是一個素數的冪=pm

。有限域的階對應的素數為有限域的特征Char(GF(pm))，即最小的正數n：使得滿足n個元素相加為0。如何構造GF(2m)?本原多項式P(x)：一個m次不可約多項式，可以整除x2m-1+1，但是不能整除其他的xk+1(k<2m-1)?？偣灿?m個元素，這些元素為0、1、α、α2、α3…α2m-2

，其中α為本原多項式P(x)=0的根。

GF(23)的本原多項式P(x)=x3+x+1，α為本原多項式

P(x)=0的根。33RS碼：伽羅瓦域例GF(23)GF(23

)元素元素mod(α3+α+1)二進制對應代碼00(000)1=α01(001)α1α1(010)α2α2(100)α3α+1(011)α4α2+α(110)α5α2+α+1(111)α6α2+1(101)所有運算都在域中進行，如GF(23)域中運算：加法：α+α4=α(1+α3)=αα=α2減法：α-α4=α+α4=α(1+α3)=α2乘法：α4α3=α4+3=α7=αα6=α(α2+1)=α3+α=1除法：α4/α=α3RS碼：RS(n,k)34

RS碼是一種擴展的非二進制（多進制）BCH碼，在GF(2m)中運算，常用RS(n,k)來表示，如RS(255,233)。

BCH是循環(huán)碼的一個子集，基于有限域而構建，可以糾正多個比特差錯，用于衛(wèi)星通信、DVD、磁盤、二維條形碼等。n為碼長，每個符號為有限域中的某個元素，由m(=8)位二進制串表示·

線性分組碼：n*m個比特為一組，每個符號由m個比特組成，總共n個符號。k為碼字中信息部分的符號個數。K=n-k為校驗（監(jiān)督）部分符號的個數。最小碼距為n-k+1。t=K/2為能糾正的錯誤符號的個數。

RS碼可用于CD、DVD、藍光CD等消費電子、DSL、WiMAX等。RS碼：編碼原理

編碼過程：信息多項式M(x)xn-k除以生成多項式G(x)的余式為校驗部分。–生成多項式

例：考慮一個GF(23)上的RS(6,4)碼，信息部分的符號為m3、m2、m1、m0，而校驗部分符號為q1、q0。信息碼多項式為M(x)=m3x3

+m2x2

+m1x1

+m0余數多項式為R(x)=q1x+q0生成多項式G(x)=(x-α)(x-α2)，偏移量K0=1因此有：m3x5

+m2x4

+m1x3

+m0

x2

+q1x+q0

=(x-α)(x-α2)Q(x)35RS碼：編碼原理（續(xù)）–x分別取α和α2，則得到校驗方程：即：m3α5

+

m2α4

+

m1α3

+

m0α2+

q1α

+

q0

=

0m3α10

+

m2α8

+

m1α6

+

m0α4+

q1α2

+

q0

=

0求解得：q1

=m3α5

+m2α5

+m1α0

+m0α4q0

=m3α

+m2α3

+m1α0

+m0α3假定信息符號取值分別是m3=α1，m2=α2，m1=α3，m0=α4，則校驗符號為q1=α6，q0=1。–接收時的校正子可按下式計算s0

=

m3α5

+

m2α4

+

m1α3

+

m0α2+

q1α

+

q0s1

=

m3α10

+

m2α8

+

m1α6

+

m0α4+

q1α2

+

q0需進一步根據校正子來推算錯誤位置和錯誤值。36以卷積碼（2,1,3）為例編碼器的生成序列：gi=(gi0，gi1，gi2，…，gim),i=0,1·

g0=(1

0

1

1),

g1=(1

1

1

1)·

編碼方程：v0=u g0

,

v1=u

g1

其中 為離散卷積輸入的信息序列u=(u0，u1，u2，…)，則輸出序列 v=(v00,v01,v10,v11,v20,v21,…)在時刻k≥0有：v0k=uk+

uk-2

+

uk-3v1k=uk

+

uk-1

+

uk-2

+

uk-3卷積碼：編碼器gg1238半無限矩陣，無限行和列，完全由第一行決定卷積碼：生成矩陣矩陣形式：v=uG

如果輸入u的長度為b，生成矩陣G有b行m+b列，輸出序列v長度為m+b。G的相鄰行中，下一行在上一行的基礎上向右移動n(=2)個位置。39約束度：(m+1)*k卷積碼40

除了采用前面的生成器序列、生成矩陣等解析法來描述卷積碼外，還可以采用圖解法，包括樹狀圖、網格圖和狀態(tài)圖等。卷積碼的譯碼方法：代數譯碼方法：以一個約束度的接收序列為單位，基于生成矩陣和監(jiān)督矩陣來譯碼。概率譯碼：從信道的統(tǒng)計特性出發(fā)，以遠大于約束度的接收序列為單位，對信息碼組進行最大似然的判決。序列譯碼維特比譯碼法雖然代數譯碼所要求的設備簡單，運算量小，但其譯碼性能（誤碼）要比概率譯碼方法差許多。因此，目前在數字通信的前向糾錯中廣泛使用的是概率譯碼方法。數據鏈路協(xié)議41

有關數據鏈路層協(xié)議的這部分內容，主要是面向連接服務中的可靠性和流量控制，包括：停等協(xié)議滑動窗口協(xié)議停等協(xié)議停等協(xié)議（Stop-and-Wait）–發(fā)送者在發(fā)送一個幀之后停下來，等待對方確認后繼續(xù)發(fā)送下一幀。while

(1)

{wait(

frame

ready);while

(1)

{transmit

(frame

i);try

{receive

(ack);}

catch

(timeout)

{

continue;

}i++;break}}while

(1)

{receive

(frame

i);transmit

(ack);}42接收方發(fā)送方停等協(xié)議（續(xù)）–如果確認在一段時間后無返回，發(fā)送者超時，重傳幀。–簡單的停等協(xié)議不包含序號，這會導致一些問題。Q:問題在哪？43停等協(xié)議（續(xù)）解決這個問題的辦法是使用順序號標識幀和確認（簡單的只需要1比特）：只有幀發(fā)送成功才能發(fā)新幀。其中發(fā)送方維護next_frame_to_send，接收方維護frame_expected。next_frame_to_send=

0;while

(1)

{wait

(frame

ready);while

(1)

{transmit

(frame

next_frame_to_send);try

{receive

(ack

n);if

(n

!=

next_frame_to_send)

continue;}

catch

(timeout)

{

continue;

}break;}next_frame_to_send

++;}frame_expected

=

0;while

(1)

{receive

(framen);ack

(frame

n);if

(n

!=

frame_expected)continue;frame_expected

++;}44接收方發(fā)送方性能分析考慮停等因素的信道利用率–設信道容量B

bps，幀長L

bit，往返傳播延遲2R秒，忽略ACK的開銷。–以衛(wèi)星信道(長肥鏈路)為例：B=50kbps,2R=0.5s,L=1kbU=1000/(1000+25000)=1/26≈4％45性能分析（續(xù)）如果考慮ACK、重傳、幀頭開銷設D為幀中有效數據長度，H為幀頭長；則數據幀長L=H+D，ACK幀長為H；T表示等待ACK的超時間隔；P1和P2分別表示數據幀和ACK丟失的概率。每個數據幀需要進行重傳的概率數據幀的平均傳輸次數、重傳次數46

為了使得不會出現(xiàn)誤重傳，超時間隔T必須取得足夠大，即T≥H/B

+2R，U要達到最大值，T越小越好，取T=H/B

+2R。–第一個因子表示停等的因素；第二個表示出錯重傳的因素；第三個為幀頭的開銷。性能分析（續(xù)）47

進一步假設信道上每比特的誤碼率為E，且各比特相互獨立，即：1-P1=(1-E)H+D，1-P2=(1-E)H，此時的利用率：–假設H、B、T、E不變，可求得使U最大的D值，即最佳幀數據長度Dopt

：令48（設計最佳D的考慮因素）性能分析（續(xù)）

考慮幀頭開銷的ACK會影響信道利用率，而大部分的通信是雙向數據通信，因此可以使用捎帶確認

(piggyback)：ACK幀通常可由反向發(fā)送的數據幀頭中一起捎帶回來。但有時完全的捎帶確認并不能工作很好，如教材P102圖3.10例中假設不支持單獨ACK導致大量重復發(fā)送，仍然需要單獨的ACK幀。49性能分析（續(xù)）滑動窗口

停等協(xié)議在開始傳輸一個數據幀到確認回來這一段時間里必須等待，傳播時間遠大于傳輸時間的時候會帶來很大的浪費。管道（Pipelining）發(fā)送方在等待確認幀回來之前可以連續(xù)發(fā)送多個數據幀序號位數要求大于等于發(fā)送者要求能夠緩存那些已經發(fā)送的但是沒有確認的幀。50滑動窗口（續(xù)）如何進行pipelined的差錯恢復？–回退N

(Go

Back

N,GBN)·

接收方只允許順序接收，也就是說如果一幀出錯，則它后面的N幀盡管可能正確到達接收方，但被直接丟棄，不發(fā)送確認。發(fā)送方將超時，按序重傳所有未被確認的幀。接收方可以不發(fā)前面的Ack而直接發(fā)后面的Ack。51滑動窗口（續(xù)）–選擇重傳(Selective

Repeat,SR)·

若某一幀出錯，后面送來的正確幀不是簡單地丟棄，而是緩存在接收緩沖區(qū)，當發(fā)送方意識到壞幀后，只重傳壞幀。一旦重傳的幀收到后，接受方與原先已收到但暫存在緩沖區(qū)中的其余幀一起按正確的順序遞交。52滑動窗口（續(xù)）滑動窗口的形成序號計數（n比特）是有限的，將會回繞。發(fā)送緩沖區(qū)和接收緩沖區(qū)是有限的。從而形成發(fā)送窗口、接收窗口滑動窗口例停等協(xié)議可以看成是一個發(fā)送窗口=接收窗口=1的滑動窗口協(xié)議。GBN為發(fā)送窗口≤2n-1、接收窗口=1的滑動窗口協(xié)議。SR協(xié)議：1≤接收窗口≤發(fā)送窗口≤2n-1。

TCP使用順序號、累加確認、檢驗和和超時重傳機制，和GBN非常類似，但是許多TCP的實現(xiàn)都緩沖那些收到的但失序的TCP段。0

1

2

3

4

5

6

7

0

1

…1

2…發(fā)送窗口53接收窗口窗口是動態(tài)滑動的、大小是不固定的，但有限的。實際上，發(fā)送窗口即已發(fā)送、尚未確認的幀；接收窗口是可用的接收緩沖區(qū)大小。數據鏈路層協(xié)議：HDLCHDLC（High-Level

Data

Link

Control）可提供面向連接和無連接的服務。面向比特的同步規(guī)程：01111110地址：標識目的節(jié)點或源節(jié)點（主站/從站），最低(E)為擴展位?？刂疲褐赋鰧儆谀欠N幀·

P(oll)/F(inal)：主站發(fā)出時表示P，如果為1要求對方響應；從站發(fā)出時示F，為1表示響應結束。

信息I幀：攜帶用戶數據，幀的序號在N(S)中。并且支持捎帶確認：N(R)表示之前的所有幀都正確。監(jiān)控S幀：控制傳輸，亦可實現(xiàn)單獨確認。（沒有數據部分）無編號U幀：其它鏈路控制功能M=00000：UI（無編號信息）幀N(S)P/F

N(R)I幀

0S幀

1

0 類型

P/F

N(R)3U幀

1

1

MP/F

M35532HDLC（續(xù)）56三種站點：主站：控制鏈路的操作，發(fā)送COMMAND。從站：響應主站的控制，發(fā)送RESPONSE。主從站：主站和從站的結合。兩種鏈路配置非平衡配置：一個主站，多個從站。平衡配置：兩個主從站。3種數據傳輸模式

正常響應模式NRM：用于非平衡配置中。主站發(fā)起數據傳輸，從站響應。

異步響應模式ARM：用于非平衡配置中，從站也可發(fā)起數據傳輸，但主站維護鏈路。很少使用。異步平衡模式ABM：用于平衡配置，任何一個站點可以發(fā)起數據傳輸。57連接建立和釋放（U幀）數據傳輸數據傳輸:RNRS幀：RR(00,Receive