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

1、Public InfrastructureBuildingsComputersPeopleSmart CardsHomesAppliancesTransportationVehiclesVendingMachines$.數(shù)據(jù)通信與網(wǎng)絡(luò)1數(shù)據(jù)通信Data Communications數(shù)據(jù)鏈路控制7. Data Link Control 線路規(guī)程 差錯(cuò)控制 流量控制2為何需要數(shù)據(jù)鏈路控制？我們的討論迄今涉及的是，在一條傳輸鏈路上傳送信號(hào)僅靠物理層的同步和接口技術(shù)是不夠的本單元中，我們把重點(diǎn)轉(zhuǎn)向在一條數(shù)據(jù)通信鏈路上傳送數(shù)據(jù)為了有效地進(jìn)行數(shù)字?jǐn)?shù)據(jù)通信，還需涉及控制和管理信息交換的更多內(nèi)容數(shù)據(jù)鏈路層與數(shù)

2、據(jù)鏈路控制協(xié)議 3數(shù)據(jù)鏈路層4數(shù)據(jù)鏈路層的功能線路規(guī)程(Line Discipline)針對(duì)某種線路配置對(duì)鏈路系統(tǒng)進(jìn)行協(xié)調(diào)決定什么設(shè)備可發(fā)送以及何時(shí)發(fā)送流量控制(Flow Control)決定發(fā)送方收到確認(rèn)之前可以發(fā)送多少數(shù)據(jù)確保接收方應(yīng)答幀正確無(wú)誤到達(dá)差錯(cuò)控制(Error Control)檢錯(cuò)與糾錯(cuò)通知發(fā)送方重發(fā)丟失或出錯(cuò)的幀56要點(diǎn)線路規(guī)程詢問(wèn)/確認(rèn), 輪詢/選擇流量控制停-等, 滑動(dòng)窗口差錯(cuò)檢測(cè)奇偶檢驗(yàn), 循環(huán)冗余檢驗(yàn)差錯(cuò)控制 (自動(dòng)重發(fā)請(qǐng)求 - ARQ)停-等ARQ, 回退N幀ARQ, 選擇-拒絕ARQ高級(jí)數(shù)據(jù)鏈路控制 (HDLC)基本特性, 幀結(jié)構(gòu), 操作其它數(shù)據(jù)鏈路控制協(xié)議LAPB

3、, LAPD, LLC, FR, ATM, BSC, PPP, XMODEM7需求與目標(biāo)線路配置幀同步流量控制差錯(cuò)控制尋址同一鏈路上的數(shù)據(jù)與控制鏈路管理87.1 線路規(guī)程兩種實(shí)現(xiàn)方式詢問(wèn)/確認(rèn)(ENQ/ACK)對(duì)等通信中采用平衡模式點(diǎn)到點(diǎn)專用鏈路輪詢/選擇(Poll/Select)用于主從式通信非平衡模式多點(diǎn)鏈路9ENQ/ACK10ENQ/ACK線路規(guī)程11輪詢/選擇如何工作多點(diǎn)線路規(guī)程12多點(diǎn)選擇13多點(diǎn)輪詢147.2 流量控制流量控制是指一組過(guò)程限制發(fā)送方在等待確認(rèn)前能夠發(fā)送的數(shù)據(jù)量保證發(fā)送實(shí)體發(fā)送的數(shù)據(jù)不超出接收實(shí)體接收數(shù)據(jù)的能力防止緩沖溢出幀傳輸模型無(wú)錯(cuò)傳輸發(fā)生丟失與差錯(cuò)的傳輸 15M

4、odel of Frame Transmission譯成混淆？篡改、歪曲16傳輸時(shí)間與傳播時(shí)間Transmission time tframe將一幀所有比特發(fā)送到傳輸媒體所花的時(shí)間與幀的長(zhǎng)度成正比傳輸時(shí)間 = L / RL=以比特為單位的幀長(zhǎng)度Propagation time (propagation delay) tprop一個(gè)比特通過(guò)鏈路的時(shí)間傳播時(shí)間 = d / Vd=以米為單位的鏈路距離V=以m/s 為單位的傳播速度17流量控制方法停止等待一次發(fā)送一幀窗口滑動(dòng)窗口一次發(fā)送若干幀滑動(dòng)窗口固定大小信用量一次發(fā)送若干幀滑動(dòng)窗口尺寸動(dòng)態(tài)變化18停止等待流量控制源站發(fā)送數(shù)據(jù)幀目的站收到該幀后給予

5、確認(rèn)(ACK)回答源站等待并收到ACK 后，再發(fā)送下一幀 目的站通過(guò)不回送ACK來(lái)終止流量對(duì)于少量的長(zhǎng)幀行之有效19停止等待示意20分片大的數(shù)據(jù)塊可以分成小的幾塊有限的緩沖大小快速檢測(cè)到差錯(cuò) (收到整個(gè)幀之后)出錯(cuò)時(shí), 只需重傳較小的幀防止一個(gè)站長(zhǎng)時(shí)間占據(jù)傳輸媒體對(duì)單個(gè)報(bào)文使用多幀時(shí)，停止等待流量控制效率低下幀長(zhǎng)度(Frame size)21停止等待鏈路利用率(1)鏈路的比特長(zhǎng)度bit length = R(d/v)R:bps; d:munguided media: v=3x108 m/sguided media: v=2x108 m/s傳送數(shù)據(jù)的總時(shí)間 T=nTF =n(tframe+ 2t

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

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

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

9、錯(cuò)P3 : 無(wú)未檢測(cè)出比特錯(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ò)碼32差錯(cuò)檢測(cè)編碼參見(jiàn)通信系統(tǒng)引論“1.11 編碼”一節(jié)編碼分類線性與非線性編碼分組碼與卷積碼循環(huán)碼(CRC)與非循環(huán)碼(VRC/LRC/checksum)編碼糾錯(cuò)能力碼距（漢明距離）編碼性能33奇偶檢驗(yàn)奇偶檢驗(yàn)比特的值使得字符中值為1的比特個(gè)數(shù)是偶數(shù) (偶檢驗(yàn)) 或奇數(shù) (奇檢驗(yàn)) 檢測(cè)單比特錯(cuò)和奇數(shù)個(gè)比特突發(fā)錯(cuò)無(wú)法檢測(cè)出偶數(shù)個(gè)比特錯(cuò)34循環(huán)冗余檢驗(yàn)對(duì)于一個(gè) k 比特的塊，發(fā)送方

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

11、xample in textbook (p.158) Another example on this slide動(dòng)畫演示38多項(xiàng)式CRC過(guò)程可以描述為 例如, M=110011 M(X)=X5+ X4 +X+1P=11001 P(X)=X4+ X3 +139Polynomial and Divisor40可檢測(cè)出的差錯(cuò)所有的下列差錯(cuò)都不能被一個(gè)適當(dāng)選擇的P(x)所整除，因此能被檢測(cè)出:任意單比特錯(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ā)長(zhǎng)度小于P(x)長(zhǎng)度時(shí), 即小于或等于 FCS (CRC)之時(shí)大多數(shù)較長(zhǎng)的突發(fā)錯(cuò)41

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

13、ion (FEC)Automatic Repeat Request (ARQ)Hybrid Error Correction (HEC)三種標(biāo)準(zhǔn)化的 ARQStop-and-wait ARQGo-back-N ARQSelective reject ARQ46停止等待ARQ源站發(fā)送單幀等待 ACK確認(rèn)如果接收到的幀損壞, 丟棄該幀發(fā)送方有一個(gè)計(jì)時(shí)器如果超時(shí)仍未收到 ACK, retransmit重傳該幀如果ACK損壞, 發(fā)送方無(wú)法辨別發(fā)送方重傳該幀接收方接收了該幀的兩份副本交替使用ACK0和ACK1, 并丟棄重復(fù)的幀 動(dòng)畫演示47停止等待ARQ -圖例說(shuō)明剛才描述的兩類差錯(cuò)的例子1:第三幀丟失

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

15、)第i幀丟失發(fā)送方發(fā)送第 i+1幀接收方收到第 i+1幀，失序接收方發(fā)送 REJ-i發(fā)送方回退到第 i 幀并重傳52回退N幀ARQ 丟失的幀 (2)第 i 幀丟失且無(wú)其它幀要發(fā)送接收方什么也沒(méi)收到，既不回送RR也不回送REJ發(fā)送方超時(shí)并發(fā)送 P比特置1的RR幀發(fā)送方將該RR解釋為命令，要求接收方發(fā)送含有其期望的下一幀(第 i 幀)的編號(hào)的RR 發(fā)送方然后重傳第 i 幀53回退N幀ARQ 損壞的RR接收方收到第 i 幀并發(fā)送RR (i+1) ，該RR丟失確認(rèn)是累積的, 發(fā)送方在第 i 幀確認(rèn)超時(shí)之前可能收到下一個(gè)確認(rèn)RR (i+n) 如果發(fā)送方超時(shí)，發(fā)送P比特置1的RR幀在復(fù)位過(guò)程初始化之前這可

16、能重復(fù)若干次54回退N幀ARQ 損壞的REJ與前面“丟失的幀 (2)”過(guò)程相同55回退 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的RR56選擇拒絕ARQ亦稱選擇重傳僅重傳拒絕的幀接收方接受后續(xù)幀并給予緩存使重傳最小化接收方必須維護(hù)足夠大的緩存，且必須包含將重傳幀以恰當(dāng)順序重新插入的邏輯 發(fā)送方也需要具有發(fā)送失序

17、幀能力的更復(fù)雜邏輯57選擇拒絕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)備58選擇拒絕ARQ的窗口尺寸選擇拒絕的窗口大小限制比回退N幀更嚴(yán)格考慮一個(gè)為7的窗口大小 (23-1)發(fā)送方發(fā)送第0幀至第6幀到接收方接收方收到全部七幀并以RR7給予累積確認(rèn) ， 且已將接收窗口前以接受第 7, 0, 1, 2, 3, 4和5幀由于突發(fā)噪聲, RR7 丟失發(fā)送方超時(shí)并重傳第0幀上述的問(wèn)題是發(fā)送窗口與接

18、收窗口之間有重疊為克服該問(wèn)題，最大窗口大小不應(yīng)大于序號(hào)范圍的一半597.5 高級(jí)數(shù)據(jù)鏈路控制HDLCISO 3009, ISO 433560HDLC 站點(diǎn)類型Primary station（主站）控制和管理鏈路的操作發(fā)出的幀稱為命令為每個(gè)從站維持一條獨(dú)立的鏈路Secondary station （從站）在主站控制之下操作發(fā)出的幀稱為響應(yīng)Combined station （混合站）可以發(fā)出命令和響應(yīng)61HDLC 鏈路配置非平衡一個(gè)主站和一個(gè)或多個(gè)從站支持全雙工和半雙工平衡兩個(gè)混合站支持全雙工和半雙工62HDLC傳送方式 (1)正常響應(yīng)方式 (NRM)非平衡配置主站發(fā)起到從站的數(shù)據(jù)傳送從站只通過(guò)傳

19、輸數(shù)據(jù)來(lái)響應(yīng)來(lái)自主站的命令用于多點(diǎn)線路計(jì)算機(jī)主機(jī)作為主站終端作為從站63HDLC傳送方式 (2)異步平衡方式 (ABM)平衡配置任一站都可發(fā)起傳輸而無(wú)需接收站的許可應(yīng)用更廣泛無(wú)輪詢的額外開(kāi)銷64HDLC傳送方式 (3)異步響應(yīng)方式 (ARM)非平衡配置從站可以發(fā)起傳輸而無(wú)需主站允許主站對(duì)線路全權(quán)負(fù)責(zé)很少使用65幀結(jié)構(gòu)同步傳輸所有傳輸均以幀的形式單一的幀格式能滿足所有數(shù)據(jù)和控制信息的交換66幀結(jié)構(gòu)圖示67標(biāo)志字段在幀兩端起定界作用標(biāo)志一幀的結(jié)束同時(shí)標(biāo)志下一幀開(kāi)始接收方搜索標(biāo)志序列用于一幀起始的同步對(duì)包含有01111110 的數(shù)據(jù)進(jìn)行比特填充 (bit stuffing) ，避免與標(biāo)志相混淆每5個(gè)

20、連續(xù)的1序列之后插入0 接收方檢測(cè)到5個(gè)連續(xù)1后判斷下一個(gè)比特若為 0，表示是數(shù)據(jù)，刪除該0若為 1，且第七個(gè)比特為 0，當(dāng)作標(biāo)志若第六和第七個(gè)比特都為 1，發(fā)送方指示異常中止68舉例比特填充的例子可能出錯(cuò)的例子69地址字段標(biāo)識(shí)發(fā)送該幀或準(zhǔn)備接收該幀的從站通常為8比特長(zhǎng)可以擴(kuò)展為多個(gè)7比特每個(gè)八比特組的LSB 為1或0指明其是否最后一個(gè)八比特組全1 (11111111) 為廣播地址70控制字段因不同幀類型而異Information 信息幀，要傳送給用戶 (相鄰高層)的數(shù)據(jù)在信息幀中捎帶流量控制和差錯(cuò)控制信息Supervisory 監(jiān)控幀，不使用捎帶技術(shù)時(shí)的ARQ四類：RR、RNR、REJ、SR

21、EJUnnumbered 無(wú)編號(hào)幀，增補(bǔ)的鏈路控制功能五類：方式設(shè)定、初始化、拆鏈、無(wú)編號(hào)交換、雜類控制字段的第一個(gè)或前兩個(gè)比特指示幀類型其余比特隨后解釋71控制字段圖示72輪詢/結(jié)束比特Poll/Final Bit 用處依賴于前因后果命令幀作為P比特解釋置1 向?qū)Φ葘?shí)體請(qǐng)求 (輪詢) 響應(yīng)幀響應(yīng)幀作F比特解釋置1 指示本響應(yīng)幀 是對(duì)請(qǐng)求命令的響應(yīng)73信息字段僅包含于信息幀和某些無(wú)編號(hào)幀中必須包含整數(shù)個(gè)八比特組變長(zhǎng)74幀檢驗(yàn)序列字段FCS差錯(cuò)檢測(cè)16比特CRC可選的32比特CRC75HDLC操作在兩個(gè)站點(diǎn)間交換信息幀、監(jiān)控幀和無(wú)編號(hào)幀三階段初始化數(shù)據(jù)傳送拆除連接（拆鏈、斷連）76初始化初始化可

22、由任意一方發(fā)出六個(gè)置位命令之一來(lái)請(qǐng)求這些命令有三個(gè)作用通知對(duì)方已請(qǐng)求了初始化指定了所需的三種傳送方式之一NRM，ABM，ARM指定是使用3比特還是7比特的序號(hào)對(duì)方的響應(yīng) 接受該請(qǐng)求并發(fā)回一個(gè)無(wú)編號(hào)確認(rèn)(UA)幀給發(fā)起方拒絕該請(qǐng)求并發(fā)回一個(gè)拆鏈 (DM)幀給發(fā)起方77數(shù)據(jù)傳送當(dāng)請(qǐng)求了初始化且被接受后，建立起一個(gè)邏輯連接雙方可以開(kāi)始發(fā)送信息幀中的用戶數(shù)據(jù)，幀序號(hào)從0開(kāi)始信息幀的N(S)和N(R) 字段是支持流量控制和差錯(cuò)控制的序號(hào) 信息幀的序號(hào)以8或128為模順序編號(hào)，取決于使用的是3比特序號(hào)還是8比特序號(hào)監(jiān)控幀 (RR, RNR, REJ, SREJ) 也用于流量控制和差錯(cuò)控制78拆鏈任一方的H

23、DLC模塊都可以發(fā)起拆鏈如果出現(xiàn)某種故障，自己發(fā)起或者根據(jù)高層用戶請(qǐng)求發(fā)送一個(gè)DISC幀宣布連接終止遠(yuǎn)程實(shí)體通過(guò)用一個(gè)UA幀回答來(lái)接受該拆鏈請(qǐng)求，并通知第三層用戶連接已經(jīng)終止 任何懸而未決的未確認(rèn)信息幀可能丟失，其恢復(fù)是高層的職責(zé)動(dòng)畫演示79操作舉例 (1)80操作舉例 (2)817.5 其它DLC協(xié)議 - LAPB, LAPDLink Access Procedure, Balanced (LAPB)X.25 的組成部分(ITU-T)物理級(jí)（X.21）、鏈路級(jí)（LAPB）、分組級(jí)（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比特的序號(hào) (無(wú)3比特序號(hào))16比特地址字段，包含兩個(gè)子地址一個(gè)標(biāo)識(shí)設(shè)備，一個(gè)標(biāo)識(shí)用戶 (相鄰高層)82LAPB和LAPD幀格式83其它DLC協(xié)議 - LLCLogical Li