1、數(shù)據(jù)通信與網(wǎng)絡(luò),數(shù)據(jù)通信Data Communications,數(shù)據(jù)鏈路控制 7. Data Link Control,線路規(guī)程,差錯控制,流量控制,為何需要數(shù)據(jù)鏈路控制？,我們的討論迄今涉及的是，在一條傳輸鏈路上傳送信號 僅靠物理層的同步和接口技術(shù)是不夠的 本單元中，我們把重點轉(zhuǎn)向在一條數(shù)據(jù)通信鏈路上傳送數(shù)據(jù) 為了有效地進(jìn)行數(shù)字?jǐn)?shù)據(jù)通信，還需涉及控制和管理信息交換的更多內(nèi)容 數(shù)據(jù)鏈路層與數(shù)據(jù)鏈路控制協(xié)議,數(shù)據(jù)鏈路層,數(shù)據(jù)鏈路層的功能,線路規(guī)程(Line Discipline) 針對某種線路配置對鏈路系統(tǒng)進(jìn)行協(xié)調(diào) 決定什么設(shè)備可發(fā)送以及何時發(fā)送 流量控制(Flow Control) 決定發(fā)送方

2、收到確認(rèn)之前可以發(fā)送多少數(shù)據(jù) 確保接收方應(yīng)答幀正確無誤到達(dá) 差錯控制(Error Control) 檢錯與糾錯 通知發(fā)送方重發(fā)丟失或出錯的幀,要點,線路規(guī)程 詢問/確認(rèn), 輪詢/選擇 流量控制 停-等, 滑動窗口 差錯檢測 奇偶檢驗, 循環(huán)冗余檢驗 差錯控制 (自動重發(fā)請求 - ARQ) 停-等ARQ, 回退N幀ARQ, 選擇-拒絕ARQ 高級數(shù)據(jù)鏈路控制 (HDLC) 基本特性, 幀結(jié)構(gòu), 操作 其它數(shù)據(jù)鏈路控制協(xié)議 LAPB, LAPD, LLC, FR, ATM, BSC, PPP, XMODEM,需求與目標(biāo),線路配置 幀同步 流量控制 差錯控制 尋址 同一鏈路上的數(shù)據(jù)與控制 鏈路管理,

3、7.1 線路規(guī)程,兩種實現(xiàn)方式 詢問/確認(rèn)(ENQ/ACK) 對等通信中采用平衡模式 點到點專用鏈路 輪詢/選擇(Poll/Select) 用于主從式通信非平衡模式 多點鏈路,ENQ/ACK,ENQ/ACK線路規(guī)程,輪詢/選擇如何工作,多點線路規(guī)程,多點選擇,多點輪詢,7.2 流量控制,流量控制是指一組過程 限制發(fā)送方在等待確認(rèn)前能夠發(fā)送的數(shù)據(jù)量 保證發(fā)送實體發(fā)送的數(shù)據(jù)不超出接收實體接收數(shù)據(jù)的能力 防止緩沖溢出 幀傳輸模型 無錯傳輸 發(fā)生丟失與差錯的傳輸,Model of Frame Transmission,譯成混淆？ 篡改、歪曲,傳輸時間與傳播時間,Transmission time tf

4、rame 將一幀所有比特發(fā)送到傳輸媒體所花的時間 與幀的長度成正比 傳輸時間 = L / R L=以比特為單位的幀長度 Propagation time (propagation delay) tprop 一個比特通過鏈路的時間 傳播時間 = d / V d=以米為單位的鏈路距離 V=以m/s 為單位的傳播速度,流量控制方法,停止等待 一次發(fā)送一幀窗口 滑動窗口 一次發(fā)送若干幀 滑動窗口固定大小 信用量 一次發(fā)送若干幀 滑動窗口尺寸動態(tài)變化,停止等待流量控制,源站發(fā)送數(shù)據(jù)幀 目的站收到該幀后給予確認(rèn)(ACK)回答 源站等待并收到ACK 后，再發(fā)送下一幀 目的站通過不回送ACK來終止流量 對于少

5、量的長幀行之有效,停止等待示意,分片,大的數(shù)據(jù)塊可以分成小的幾塊 有限的緩沖大小 快速檢測到差錯 (收到整個幀之后) 出錯時, 只需重傳較小的幀 防止一個站長時間占據(jù)傳輸媒體 對單個報文使用多幀時，停止等待流量控制效率低下 幀長度(Frame size),停止等待鏈路利用率(1),鏈路的比特長度 bit length = R(d/v)R:bps; d:m unguided media: v=3x108 m/s guided media: v=2x108 m/s 傳送數(shù)據(jù)的總時間 T=nTF =n(tframe+ 2tprop) TF=tprop+ tframe+ tproc+ tprop+ t

6、ack+ tproc 線路利用率或者效率 u=ntframe/n(tframe+2tprop)=tframe/(tframe+2tprop)=1/(1+2a) a= tprop/tframe transmission time歸一化 propagation time表示為變量 a,停止等待鏈路利用率(2),a的另一個表達(dá)式 圖7.2 當(dāng) a1時, 皆有: Total time=1+2a u=1/(1+2a) 例1: 求 ATM的鏈路利用率 P.179 L=424bits, d=1000km, R=155.52Mbps 例2:求LAN的鏈路利用率 L=1000bits, d=0.1km10km,

7、 R=10Mbps1Gbps 例3:求撥號數(shù)據(jù)鏈路利用率 L=1000bits, d=5000km, R=56Kbps,停止等待鏈路利用率(3),滑動窗口流量控制,當(dāng) a1, 若一次僅允許傳輸一幀，導(dǎo)致嚴(yán)重的低效率 滑動窗口流控允許連續(xù)傳送多幀 接收方緩沖長 W 發(fā)送方可以連續(xù)發(fā)送 W 幀后才需 ACK 給每幀編個號 ACK幀中包含所期望的下一幀的編號 以字段大小(k)所限定的序號 以2k為模對幀進(jìn)行編號,Sliding Window Diagram,發(fā)送方滑動窗口,當(dāng)發(fā)送出數(shù)據(jù)時，滑動窗口從左邊開始收縮； 當(dāng)收到確認(rèn)時，滑動窗口向右擴(kuò)展,接收方滑動窗口,當(dāng)接收到數(shù)據(jù)時，滑動窗口從左邊開始收縮

8、； 當(dāng)發(fā)送確認(rèn)時，滑動窗口向右擴(kuò)展,滑動窗口實例,Window size is limited to 7(2k-1) See P.165,又一個滑動窗口實例,滑動窗口的改進(jìn),接收方可以通過不允許繼續(xù)發(fā)送(Receive Not Ready) 來對幀進(jìn)行確認(rèn) 必須送一個正常確認(rèn)給予恢復(fù) 如雙向發(fā)送, 使用 piggybacking (捎帶確認(rèn)) 如無數(shù)據(jù)發(fā)送，使用確認(rèn)幀，使用確認(rèn)幀 如果只送數(shù)據(jù)而不需發(fā)送確認(rèn)，則重送上一個確認(rèn)編號，或者設(shè)置ACK 有效標(biāo)志 (TCP),7.3 差錯檢測,定義幾個概率 Pb: 單比特錯概率 P1: 無比特錯概率 P2: 一個或多個未檢測出的比特錯 P3 : 無未檢

9、測出比特錯的概率 當(dāng)不采取檢錯措施時 P3 =0, P1 =(1- Pb) F, P2 =1- P1 例子: 在一條ISDN 鏈路中Pb=10-6 ，求 P1 和P2 檢錯技術(shù) 發(fā)送器增加附加的比特，構(gòu)成檢錯碼,差錯檢測編碼,參見通信系統(tǒng)引論“1.11 編碼”一節(jié) 編碼分類 線性與非線性編碼 分組碼與卷積碼 循環(huán)碼(CRC)與非循環(huán)碼(VRC/LRC/checksum) 編碼糾錯能力 碼距（漢明距離） 編碼性能,奇偶檢驗,奇偶檢驗比特的值使得字符中值為1的比特個數(shù)是偶數(shù) (偶檢驗) 或奇數(shù) (奇檢驗) 檢測單比特錯和奇數(shù)個比特突發(fā)錯 無法檢測出偶數(shù)個比特錯,循環(huán)冗余檢驗,對于一個 k 比特的塊

10、，發(fā)送方產(chǎn)生 n 比特序列, 稱為 幀檢驗序列 (FCS) 或 CRC 發(fā)送能被某個數(shù)除盡的 k+n 個比特 接收方用該數(shù)去除收到的幀 如無余數(shù)，則認(rèn)為無錯 三種表達(dá)方式 模 2算術(shù)運(yùn)算（Modulo 2 arithmetic） 多項式（Polynomial） 數(shù)字邏輯（digital logic）,模 2算術(shù),加, 減, 乘, 除 模 2 算術(shù)運(yùn)算使用無進(jìn)位或借位的二進(jìn)制加減法 異或 運(yùn)算 模 2 除法 此時定義 T=要傳送的(k+n)比特幀, 其中 nk M=k比特報文, T的前k 個比特 R=n比特 FCS, T 的后n 個比特 P=n+1比特的比特模式, 預(yù)先確定的除數(shù),CRC,Bin

11、ary Division,An example in textbook (p.158) Another example on this slide,動畫演示,多項式,CRC過程可以描述為 例如, M=110011 M(X)=X5+ X4 +X+1 P=11001 P(X)=X4+ X3 +1,Polynomial and Divisor,可檢測出的差錯,所有的下列差錯都不能被一個適當(dāng)選擇的P(x)所整除，因此能被檢測出: 任意單比特錯 任意雙比特錯, 當(dāng) P(x) 至少有3個 1時 任意奇數(shù)個錯, 當(dāng) P(x) 包含因式 (x+1)時 任意突發(fā)錯,當(dāng)突發(fā)長度小于P(x)長度時, 即小于或等于

12、FCS (CRC)之時 大多數(shù)較長的突發(fā)錯,Standard Polynomials,數(shù)字邏輯,CRC過程可以表示為除法電路, 由異或門和一個移位寄存器組成 電路如下實現(xiàn) 寄存器包含n 比特, 等于 FCS長度 可達(dá) n 個異或門, 取決于除數(shù)多項式中的項有或無 具有移位寄存器的電路用于除法，除數(shù)多項式 P(X)=X5+X4+X2+1 報文 1010001101 M(X)=X9+X7+X3+X2+ 1,General CRC Division Circuit,7.4 差錯控制,檢錯與糾錯的機(jī)制 兩類差錯 幀的丟失 損壞的幀 最常用技術(shù) 差錯檢測 肯定確認(rèn) 超時重傳 否定確認(rèn)并重傳,差錯控制 (

13、續(xù)),三種主要的差錯控制 Forward Error Correction (FEC) Automatic Repeat Request (ARQ) Hybrid Error Correction (HEC) 三種標(biāo)準(zhǔn)化的 ARQ Stop-and-wait ARQ Go-back-N ARQ Selective reject ARQ,停止等待ARQ,源站發(fā)送單幀 等待 ACK確認(rèn) 如果接收到的幀損壞, 丟棄該幀 發(fā)送方有一個計時器 如果超時仍未收到 ACK, retransmit重傳該幀 如果ACK損壞, 發(fā)送方無法辨別 發(fā)送方重傳該幀 接收方接收了該幀的兩份副本 交替使用ACK0和ACK1

14、, 并丟棄重復(fù)的幀 動畫演示,停止等待ARQ -圖例,說明剛才描述的兩類差錯的例子 1: 第三幀丟失或損壞，無ACK 超時并重傳 2: ACK0 丟失 超時并重傳,停止等待ARQ 優(yōu)缺點,簡單 低效,回退N幀ARQ,基于滑動窗口動畫演示 如果無錯, 通常采用捎帶確認(rèn) ACK 期待下一幀 (RR=receive ready) 使用窗口控制outstanding frame的數(shù)目 懸而未決的幀，即尚未確認(rèn)的幀 如果出錯, 以拒絕給予回應(yīng) (REJ=rejection) 接收方丟棄該幀以及后續(xù)的幀, 直到錯幀正確收到 發(fā)送方必須回退并重發(fā)該幀及后續(xù)幀 為何回退？,回退N幀ARQ 損壞的幀,接收方檢測

15、到第i幀出錯 接收方發(fā)送 REJ-i 發(fā)送方接收到 REJ-i 發(fā)送方重傳第i幀及所有的后續(xù)幀,回退N幀ARQ 丟失的幀 (1),第i幀丟失 發(fā)送方發(fā)送第 i+1幀 接收方收到第 i+1幀，失序 接收方發(fā)送 REJ-i 發(fā)送方回退到第 i 幀并重傳,回退N幀ARQ 丟失的幀 (2),第 i 幀丟失且無其它幀要發(fā)送 接收方什么也沒收到，既不回送RR也不回送REJ 發(fā)送方超時并發(fā)送 P比特置1的RR幀 發(fā)送方將該RR解釋為命令，要求接收方發(fā)送含有其期望的下一幀(第 i 幀)的編號的RR 發(fā)送方然后重傳第 i 幀,回退N幀ARQ 損壞的RR,接收方收到第 i 幀并發(fā)送RR (i+1) ，該RR丟失

16、確認(rèn)是累積的, 發(fā)送方在第 i 幀確認(rèn)超時之前可能收到下一個確認(rèn)RR (i+n) 如果發(fā)送方超時，發(fā)送P比特置1的RR幀 在復(fù)位過程初始化之前這可能重復(fù)若干次,回退N幀ARQ 損壞的REJ,與前面“丟失的幀 (2)”過程相同,回退 N幀ARQ - 圖例,回退 N幀ARQ 幀流的一個例子 由于線路的傳播時延，待RR-I或REJ-i 返達(dá)發(fā)送方時, 發(fā)送方已發(fā)送了第i+1幀及隨后的幀 第 4 幀損壞或丟失 第5 幀和第 6 幀到達(dá)，因失序而丟棄 當(dāng)?shù)?幀到達(dá)時，接收方立即發(fā)送REJ-4 發(fā)送方收到REJ-4，重傳第5 、6 幀 RR 7 損壞或丟失 超時, 發(fā)送P比特置1的RR,選擇拒絕ARQ,亦

17、稱選擇重傳 僅重傳拒絕的幀 接收方接受后續(xù)幀并給予緩存 使重傳最小化 接收方必須維護(hù)足夠大的緩存，且必須包含將重傳幀以恰當(dāng)順序重新插入的邏輯 發(fā)送方也需要具有發(fā)送失序幀能力的更復(fù)雜邏輯,選擇拒絕ARQ -圖例,一個例子 第4幀損壞或丟失 接收方返回 SREJ-4并接受后續(xù)幀 發(fā)送方收到 SREJ-4 并重傳第 4幀 接收方收到第4 幀并以恰當(dāng)順序?qū)⑵洳迦刖彌_ RR-1丟失發(fā) 發(fā)送方計時器超時并送 RR(P=1) 接收方發(fā)送RR-3 并作好接收第3幀的準(zhǔn)備,選擇拒絕ARQ的窗口尺寸,選擇拒絕的窗口大小限制比回退N幀更嚴(yán)格 考慮一個為7的窗口大小 (23-1) 發(fā)送方發(fā)送第0幀至第6幀到接收方 接

18、收方收到全部七幀并以RR7給予累積確認(rèn) ， 且已將接收窗口前以接受第 7, 0, 1, 2, 3, 4和5幀 由于突發(fā)噪聲, RR7 丟失 發(fā)送方超時并重傳第0幀 上述的問題是發(fā)送窗口與接收窗口之間有重疊 為克服該問題，最大窗口大小不應(yīng)大于序號范圍的一半,7.5 高級數(shù)據(jù)鏈路控制,HDLC ISO 3009, ISO 4335,HDLC 站點類型,Primary station（主站） 控制和管理鏈路的操作 發(fā)出的幀稱為命令 為每個從站維持一條獨立的鏈路 Secondary station （從站） 在主站控制之下操作 發(fā)出的幀稱為響應(yīng) Combined station （混合站） 可以發(fā)出命

19、令和響應(yīng),HDLC 鏈路配置,非平衡 一個主站和一個或多個從站 支持全雙工和半雙工 平衡 兩個混合站 支持全雙工和半雙工,HDLC傳送方式 (1),正常響應(yīng)方式 (NRM) 非平衡配置 主站發(fā)起到從站的數(shù)據(jù)傳送 從站只通過傳輸數(shù)據(jù)來響應(yīng)來自主站的命令 用于多點線路 計算機(jī)主機(jī)作為主站 終端作為從站,HDLC傳送方式 (2),異步平衡方式 (ABM) 平衡配置 任一站都可發(fā)起傳輸而無需接收站的許可 應(yīng)用更廣泛 無輪詢的額外開銷,HDLC傳送方式 (3),異步響應(yīng)方式 (ARM) 非平衡配置 從站可以發(fā)起傳輸而無需主站允許 主站對線路全權(quán)負(fù)責(zé) 很少使用,幀結(jié)構(gòu),同步傳輸 所有傳輸均以幀的形式 單一

20、的幀格式能滿足所有數(shù)據(jù)和控制信息的交換,幀結(jié)構(gòu)圖示,標(biāo)志字段,在幀兩端起定界作用 01111110 標(biāo)志一幀的結(jié)束同時標(biāo)志下一幀開始 接收方搜索標(biāo)志序列用于一幀起始的同步 對包含有01111110 的數(shù)據(jù)進(jìn)行比特填充 (bit stuffing) ，避免與標(biāo)志相混淆 每5個連續(xù)的1序列之后插入0 接收方檢測到5個連續(xù)1后判斷下一個比特 若為 0，表示是數(shù)據(jù)，刪除該0 若為 1，且第七個比特為 0，當(dāng)作標(biāo)志 若第六和第七個比特都為 1，發(fā)送方指示異常中止,舉例,比特填充的例子 可能出錯的例子,地址字段,標(biāo)識發(fā)送該幀或準(zhǔn)備接收該幀的從站 通常為8比特長 可以擴(kuò)展為多個7比特 每個八比特組的LSB

21、為1或0指明其是否最后一個八比特組 全1 (11111111) 為廣播地址,控制字段,因不同幀類型而異 Information 信息幀，要傳送給用戶 (相鄰高層)的數(shù)據(jù) 在信息幀中捎帶流量控制和差錯控制信息 Supervisory 監(jiān)控幀，不使用捎帶技術(shù)時的ARQ 四類：RR、RNR、REJ、SREJ Unnumbered 無編號幀，增補(bǔ)的鏈路控制功能 五類：方式設(shè)定、初始化、拆鏈、無編號交換、雜類 控制字段的第一個或前兩個比特指示幀類型 其余比特隨后解釋,控制字段圖示,輪詢/結(jié)束比特,Poll/Final Bit 用處依賴于前因后果 命令幀 作為P比特解釋 置1 向?qū)Φ葘嶓w請求 (輪詢) 響

22、應(yīng)幀 響應(yīng)幀 作F比特解釋 置1 指示本響應(yīng)幀 是對請求命令的響應(yīng),信息字段,僅包含于信息幀和某些無編號幀中 必須包含整數(shù)個八比特組 變長,幀檢驗序列字段,FCS 差錯檢測 16比特CRC 可選的32比特CRC,HDLC操作,在兩個站點間交換信息幀、監(jiān)控幀和無編號幀 三階段 初始化 數(shù)據(jù)傳送 拆除連接（拆鏈、斷連）,初始化,初始化可由任意一方發(fā)出六個置位命令之一來請求 這些命令有三個作用 通知對方已請求了初始化 指定了所需的三種傳送方式之一 NRM，ABM，ARM 指定是使用3比特還是7比特的序號 對方的響應(yīng) 接受該請求并發(fā)回一個無編號確認(rèn)(UA)幀給發(fā)起方 拒絕該請求并發(fā)回一個拆鏈 (DM)

23、幀給發(fā)起方,數(shù)據(jù)傳送,當(dāng)請求了初始化且被接受后，建立起一個邏輯連接 雙方可以開始發(fā)送信息幀中的用戶數(shù)據(jù)，幀序號從0開始 信息幀的N(S)和N(R) 字段是支持流量控制和差錯控制的序號 信息幀的序號以8或128為模順序編號，取決于使用的是3比特序號還是8比特序號 監(jiān)控幀 (RR, RNR, REJ, SREJ) 也用于流量控制和差錯控制,拆鏈,任一方的HDLC模塊都可以發(fā)起拆鏈 如果出現(xiàn)某種故障，自己發(fā)起 或者根據(jù)高層用戶請求 發(fā)送一個DISC幀宣布連接終止 遠(yuǎn)程實體通過用一個UA幀回答來接受該拆鏈請求，并通知第三層用戶連接已經(jīng)終止 任何懸而未決的未確認(rèn)信息幀可能丟失，其恢復(fù)是高層的職責(zé) 動畫演

24、示,操作舉例 (1),操作舉例 (2),7.5 其它DLC協(xié)議 - LAPB, LAPD,Link Access Procedure, Balanced (LAPB) X.25 的組成部分(ITU-T) 物理級（X.21）、鏈路級（LAPB）、分組級（X.25） HDLC的子集- ABM 系統(tǒng)與分組交換網(wǎng)絡(luò)節(jié)點之間的點到點鏈路 Link Access Procedure, D-Channel (LAPD) ISDN (ITU-T) ABM 總是7比特的序號 (無3比特序號) 16比特地址字段，包含兩個子地址 一個標(biāo)識設(shè)備，一個標(biāo)識用戶 (相鄰高層),LAPB和LAPD幀格式,其它DLC協(xié)議 - LLC,Logical Link Co