數(shù)據(jù)與計(jì)算機(jī)通信dcc07.ppt

1、數(shù)據(jù)通信與網(wǎng)絡(luò),數(shù)據(jù)通信Data Communications,數(shù)據(jù)鏈路控制 7. Data Link Control,線路規(guī)程,差錯(cuò)控制,流量控制,為何需要數(shù)據(jù)鏈路控制？,我們的討論迄今涉及的是，在一條傳輸鏈路上傳送信號 僅靠物理層的同步和接口技術(shù)是不夠的 本單元中，我們把重點(diǎn)轉(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ā)送以及何時(shí)發(fā)送 流量控制(Flow Control) 決定發(fā)送方

2、收到確認(rèn)之前可以發(fā)送多少數(shù)據(jù) 確保接收方應(yīng)答幀正確無誤到達(dá) 差錯(cuò)控制(Error Control) 檢錯(cuò)與糾錯(cuò) 通知發(fā)送方重發(fā)丟失或出錯(cuò)的幀,要點(diǎn),線路規(guī)程 詢問/確認(rèn), 輪詢/選擇 流量控制 停-等, 滑動(dòng)窗口 差錯(cuò)檢測 奇偶檢驗(yàn), 循環(huán)冗余檢驗(yàn) 差錯(cuò)控制 (自動(dòng)重發(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),線路配置 幀同步 流量控制 差錯(cuò)控制 尋址 同一鏈路上的數(shù)據(jù)與控制 鏈路管理,

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

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

5、量的長幀行之有效,停止等待示意,分片,大的數(shù)據(jù)塊可以分成小的幾塊 有限的緩沖大小 快速檢測到差錯(cuò) (收到整個(gè)幀之后) 出錯(cuò)時(shí), 只需重傳較小的幀 防止一個(gè)站長時(shí)間占據(jù)傳輸媒體 對單個(gè)報(bào)文使用多幀時(shí)，停止等待流量控制效率低下 幀長度(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ù)的總時(shí)間 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的另一個(gè)表達(dá)式 圖7.2 當(dāng) a1時(shí), 皆有: 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)窗口流量控制,當(dāng) a1, 若一次僅允許傳輸一幀，導(dǎo)致嚴(yán)重的低效率 滑動(dòng)窗口流控允許連續(xù)傳送多幀 接收方緩沖長 W 發(fā)送方可以連續(xù)發(fā)送 W 幀后才需 ACK 給每幀編個(gè)號 ACK幀中包含所期望的下一幀的編號 以字段大小(k)所限定的序號 以2k為模對幀進(jìn)行編號,Sliding Window Diagram,發(fā)送方滑動(dòng)窗口,當(dāng)發(fā)送出數(shù)據(jù)時(shí)，滑動(dòng)窗口從左邊開始收縮； 當(dāng)收到確認(rèn)時(shí)，滑動(dòng)窗口向右擴(kuò)展,接收方滑動(dòng)窗口,當(dāng)接收到數(shù)據(jù)時(shí)，滑動(dòng)窗口從左邊開始收縮

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

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

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

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

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

13、續(xù)),三種主要的差錯(cuò)控制 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ā)送方有一個(gè)計(jì)時(shí)器 如果超時(shí)仍未收到 ACK, retransmit重傳該幀 如果ACK損壞, 發(fā)送方無法辨別 發(fā)送方重傳該幀 接收方接收了該幀的兩份副本 交替使用ACK0和ACK1

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

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

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

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

19、令和響應(yīng),HDLC 鏈路配置,非平衡 一個(gè)主站和一個(gè)或多個(gè)從站 支持全雙工和半雙工 平衡 兩個(gè)混合站 支持全雙工和半雙工,HDLC傳送方式 (1),正常響應(yīng)方式 (NRM) 非平衡配置 主站發(fā)起到從站的數(shù)據(jù)傳送 從站只通過傳輸數(shù)據(jù)來響應(yīng)來自主站的命令 用于多點(diǎn)線路 計(jì)算機(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é)束同時(shí)標(biāo)志下一幀開始 接收方搜索標(biāo)志序列用于一幀起始的同步 對包含有01111110 的數(shù)據(jù)進(jìn)行比特填充 (bit stuffing) ，避免與標(biāo)志相混淆 每5個(gè)連續(xù)的1序列之后插入0 接收方檢測到5個(gè)連續(xù)1后判斷下一個(gè)比特 若為 0，表示是數(shù)據(jù)，刪除該0 若為 1，且第七個(gè)比特為 0，當(dāng)作標(biāo)志 若第六和第七個(gè)比特都為 1，發(fā)送方指示異常中止,舉例,比特填充的例子 可能出錯(cuò)的例子,地址字段,標(biāo)識(shí)發(fā)送該幀或準(zhǔn)備接收該幀的從站 通常為8比特長 可以擴(kuò)展為多個(gè)7比特 每個(gè)八比特組的LSB

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

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

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

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é)點(diǎn)之間的點(diǎn)到點(diǎn)鏈路 Link Access Procedure, D-Channel (LAPD) ISDN (ITU-T) ABM 總是7比特的序號 (無3比特序號) 16比特地址字段，包含兩個(gè)子地址 一個(gè)標(biāo)識(shí)設(shè)備，一個(gè)標(biāo)識(shí)用戶 (相鄰高層),LAPB和LAPD幀格式,其它DLC協(xié)議 - LLC,Logical Link Co