計算機網(wǎng)絡(luò)網(wǎng)絡(luò)近期軟件學院

1、第6講 數(shù)據(jù)鏈路層之一6a-1第6講: 數(shù)據(jù)鏈路層本講目標: r了解數(shù)據(jù)鏈路層服務(wù)原理:m錯誤檢測, 校正m共享廣播信道m(xù)鏈路層編址m可靠數(shù)據(jù)傳輸, 流量控制: done!r各類鏈路層技術(shù)的實現(xiàn)和實例概述:r鏈路層的服務(wù)r錯誤檢測, 校正r 多點訪問技術(shù)和LANr鏈路層尋址, ARPr特定的鏈路層技術(shù):m以太網(wǎng)m集線器, 網(wǎng)橋, 交換機mIEEE 802.11 LANsmPPPmATM第6講 數(shù)據(jù)鏈路層之一6a-2鏈路層: 工作環(huán)境第6講 數(shù)據(jù)鏈路層之一6a-3鏈路層: 工作環(huán)境r兩個 物理上連接的 設(shè)備:m主機-路由器, 路由器-路由器, 主機-主機r數(shù)據(jù)單元: frame（幀）applic

2、ationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframe物理鏈路數(shù)據(jù)鏈路協(xié)議接口卡第6講 數(shù)據(jù)鏈路層之一6a-4鏈路層的服務(wù)r成幀, 鏈路訪問: m將分組封裝入幀, 加上幀頭, 幀尾m如果是共享介質(zhì)，則需實現(xiàn)信道的訪問, m物理地址 放在幀首用來確定信源、信宿 不同于IP地址喔!r在兩臺物理上連接的設(shè)備之間實現(xiàn)可靠傳遞: m可靠傳遞是什么概念，回顧一下學過的知識!m不太用在誤碼率低的場合 (光纖, 某些雙絞線)m無線鏈路: 誤碼率相當高 Q: 為什么在鏈路層和端到端之間都要做可靠性的校驗?第

3、6講 數(shù)據(jù)鏈路層之一6a-5鏈路層的服務(wù) (續(xù))r流量控制: m保持收發(fā)雙方的同步r錯誤檢測: m信號衰減和噪聲會導致出錯. m接收端檢測到錯誤時: 給發(fā)送端信號要求重發(fā)或丟棄出錯幀 r錯誤校正: m接受端檢測多個位錯并加以校正 而無需要求發(fā)送端重發(fā)第6講 數(shù)據(jù)鏈路層之一6a-6鏈路層: 實現(xiàn)r通過 “adapter（網(wǎng)卡或適配器）” 實現(xiàn)me.g., PCMCIA 卡, 以太網(wǎng)卡 m一般適配器都含有: RAM, DSP 芯片, 主機的總線接口, 和鏈路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnH

4、tHnHlMHtHnHlframephys. linkdata linkprotocoladapter card第6講 數(shù)據(jù)鏈路層之一6a-7錯誤檢測EDC= 錯誤檢測校正（Error Detection and Correction (冗余數(shù)據(jù))）位D = 由檢驗位保護的數(shù)據(jù), 可包括首部字段 錯誤檢測不可能達到 100% 可靠! 協(xié)議算法可能會忽略了某些錯誤, 但比例極小 較大的 EDC 字段可以產(chǎn)生較好的檢錯和糾錯效果第6講 數(shù)據(jù)鏈路層之一6a-8奇偶校驗單比特校驗:檢測一位錯誤檢測一位錯誤兩維單比特校驗:檢測和校正單比特錯誤檢測和校正單比特錯誤00第6講 數(shù)據(jù)鏈路層之一6a-9因特網(wǎng)校

5、驗和發(fā)送端:r把數(shù)據(jù)段的內(nèi)容看成一系列16-bit的整數(shù)r校驗和: 對內(nèi)容進行累加 (1s complement sum)r 發(fā)送端將校驗和放入UDP 的checksum 字段接收端:r對接收到的數(shù)據(jù)段進行校驗和計算r檢查計算所得的校驗和與接收到值的是否相等 :mNO 出錯了mYES 沒查出錯誤. 但有可能存在錯誤? .目的: 檢測 數(shù)據(jù)段在傳輸過程中出現(xiàn)的錯誤 (注意: 僅用在傳輸層)第6講 數(shù)據(jù)鏈路層之一 6a-10校驗計算: 循環(huán)校驗碼r把數(shù)據(jù)比特串, D, 看成二進制數(shù)據(jù)r選擇一個 r+1 bit 型 (generator), G r目的: 選擇 r個 CRC位, R, 這樣m 可為

6、G 整除(modulo 2) m接收端已知 G, 用G來除 . 如果余數(shù)不為0: 查出錯誤!m可以查出所有長度不超過r+1位的突發(fā)錯誤r在實踐中被廣泛應(yīng)用 (ATM, HDCL)第6講 數(shù)據(jù)鏈路層之一 6a-11CRC 舉例如果要:D.2r XOR R = nG則等于:D.2r = nG XOR R 也就等于: 如果要讓 D.2r 被 G整除, 則需要余數(shù) RR = remainder D.2rG第6講 數(shù)據(jù)鏈路層之一 6a-12多點訪問鏈路和協(xié)議有三種類型的 “鏈路”:r點對點 ( e.g. PPP, SLIP)r廣播式 (共享線路或介質(zhì); e.g, 以太網(wǎng), 無線網(wǎng), etc.)r交換式

7、(e.g., 交換式以太網(wǎng), ATM etc)第6講 數(shù)據(jù)鏈路層之一 6a-13多點訪問協(xié)議r一條共享的通信信道 r兩個或多個結(jié)點可同時發(fā)送信號: 相互干擾 m在某一時刻只有一個結(jié)點可以成功地發(fā)送信號 r多點訪問協(xié)議:m分布式的算法來決定如何共享信道, i.e., 決定工作站何時可以發(fā)送m注意：有關(guān)共享通道的通信（協(xié)商）也必須在該通道自身上解決! m我們希望多點訪問協(xié)議能夠解決什么問題: 同步還是異步 了解其他站點的信息 健壯性 (e.g.如何對待信道錯誤) 性能第6講 數(shù)據(jù)鏈路層之一 6a-14多點訪問協(xié)議r斷言: 人類在許多場合都使用多點訪問協(xié)議 rclass can guess mult

8、iple access protocols mmultiaccess protocol 1:mmultiaccess protocol 2:mmultiaccess protocol 3:mmultiaccess protocol 4:第6講 數(shù)據(jù)鏈路層之一 6a-15MAC 協(xié)議: 分類r通道分割m將信道分割成較小的 “片” (時隙, 頻率)m將小片分給各站點使用r隨機訪問m允許沖突m從沖突中“恢復”r“排隊排隊”m嚴格協(xié)調(diào)訪問來避免沖突目標: 高效, 公平, 簡單, 分散控制第6講 數(shù)據(jù)鏈路層之一 6a-16信道分割的 MAC 協(xié)議: TDMATDMA: time division mul

9、tiple access （時分多路）r“依次” 訪問信道r每次每個站點分得固定長度的時隙 (時長 = 分組的單位傳輸時間)r未用的時隙被閑置和浪費 r例如: 6個站點的LAN, 1,3,4 有分組發(fā)送, 而 2,5,6的時隙則被閑置 第6講 數(shù)據(jù)鏈路層之一 6a-17 信道分割的 MAC 協(xié)議: FDMAFDMA: frequency division multiple access（頻分復用） r信道按頻譜分成若干頻段r每個站點分得固定的頻段r在頻段不用時該部分信道被閑置和浪費 r例如: 6各站點的 LAN, 1,3,4 發(fā)送分組, 而 2,5,6 的頻段被閑置 frequency ban

10、dstime第6講 數(shù)據(jù)鏈路層之一 6a-18信道分割 (CDMA)CDMA：Code Division Multiple Access（碼分多路） r每個用戶分得具有唯一性的 “code”; ie, 代碼集合的分割r大部分應(yīng)用在無線通信的場合 (cellular, satellite,etc)r所有用戶共享相同的頻道, 但每個用戶用自己的“碼片”序列 (ie, code) 對數(shù)據(jù)編碼r編碼信號 = (原始數(shù)據(jù)) X (碼片序列)r解碼: 編碼信號的內(nèi)積和碼片序列r允許多個用戶共存和發(fā)送信號,且相互的干擾極小 (假設(shè)信號碼呈 “正交”狀)第6講 數(shù)據(jù)鏈路層之一 6a-19CDMA 編碼/解碼第

11、6講 數(shù)據(jù)鏈路層之一 6a-20CDMA: 兩個用戶互擾的情況第6講 數(shù)據(jù)鏈路層之一 6a-21隨機訪問協(xié)議r當結(jié)點有數(shù)據(jù)要發(fā)送時：m使用信道全部的傳輸速率 R.m在諸多結(jié)點中不存在“預先”協(xié)商的機制r可能發(fā)生兩個以上結(jié)點同時傳輸 - “沖突”r隨機訪問的 MAC協(xié)議定義了: m如何檢測沖突m如何從沖突中恢復 (e.g., 通過延遲重發(fā))r隨機訪問 MAC協(xié)議的實例:m時隙ALOHAmALOHAmCSMA and CSMA/CD第6講 數(shù)據(jù)鏈路層之一 6a-22時隙 Alohar時間劃分成等長的時隙 (=分組單元傳送的時長)r對待新近到達的分組結(jié)點要: 在下一個時隙開始時傳輸 r如果沖突: 以

12、p的概率再后繼的時隙重發(fā)分組，直到成功為止.(S)成功, (C)沖突, (E) 空閑的時隙第6講 數(shù)據(jù)鏈路層之一 6a-23時隙 Aloha 的效率Q: 時隙的利用情況如何?A: 假設(shè)有 N站點有數(shù)據(jù)發(fā)送m每個站點以p的概率在時隙中傳輸數(shù)據(jù)m傳輸成功的概率 S為:對單個結(jié)點來說: S= p (1-p)(N-1) 對N個節(jié)點中的任何一個： S = 概率 (僅有一個站點傳輸?shù)? = N p (1-p)(N-1) 選擇最佳的 p 當 n - infty . = 1/e = .37最佳情況: 信道的使用率為 37%!第6講 數(shù)據(jù)鏈路層之一 6a-24純 (無時隙) ALOHAr無時隙 Aloha: 簡

13、單, 沒有同步信號r需要傳輸分組時:m 立即發(fā)送而不必等待時隙的開始r沖突的概率增加了:m在 t0 時刻發(fā)送的分組與在 t0-1, t0+1時刻發(fā)送的分組沖突第6講 數(shù)據(jù)鏈路層之一 6a-25純 Aloha (續(xù))P(給定節(jié)點的成功率) = P(節(jié)點傳輸) . P(無其他節(jié)點在 p0-1,p0時刻傳輸） . P(無其他節(jié)點在p0-1,p0時刻傳輸） = p . (1-p) . (1-p) P(在N結(jié)點中任意結(jié)點的成功率) = N p . (1-p) . (1-p) 選擇最佳的 p 當 n - infty . = 1/(2e) = .18 S = throughput = “goodput” (

14、success rate)G = offered load = Np0.51.01.52.00.10.20.30.4Pure AlohaSlotted Aloha協(xié)議 限制了信道吞吐量的有效利用!第6講 數(shù)據(jù)鏈路層之一 6a-26CSMA: Carrier Sense Multiple AccessCSMA: （載波檢測多路訪問）發(fā)送前偵聽:r如果信道閑置: 發(fā)送整個分組r如果信道忙, 推遲發(fā)送 m堅持性 CSMA: 當信道閑置時，以p的概率立即重試 (可能導致不穩(wěn)定)m非堅持性 CSMA: 在某個隨機間隔以后再試r為人處事的規(guī)則之一: 不要打斷別人的發(fā)言!第6講 數(shù)據(jù)鏈路層之一 6a-27C

15、SMA 的沖突沖突可能發(fā)生在:由于傳播延遲兩個節(jié)點可能聽不到對方的發(fā)送沖突:整個分組的傳輸時間被浪費以太網(wǎng)結(jié)點間的時空圖注意:這里的沖突概率是由距離和 傳播延遲來決定的第6講 數(shù)據(jù)鏈路層之一 6a-28CSMA/CD (Collision Detection，沖突檢測)CSMA/CD:m在沖突發(fā)生后，短時間內(nèi)可探測到m立即中斷傳輸, 減少信道的時間浪費 m堅持性或非堅持性重傳r沖突檢測: m在有線 LAN中簡便易行: 檢測信號強度, 比較收、發(fā)的信號m在無線 LAN比較困難: 傳輸時接收器是關(guān)閉的r人類社會的范例: 彬彬有禮的交談?wù)?第6講 數(shù)據(jù)鏈路層之一 6a-29CSMA/CD 沖突檢測第6講 數(shù)據(jù)鏈路層之一 6a-30“輪轉(zhuǎn)式” MAC 協(xié)議信道分割的 MAC 協(xié)議:m在重負荷時共享信道的效率高m在輕負荷時效率低: 延遲了信道訪問, 當只有一個結(jié)點激活時，分到的帶寬只有信道帶寬的1/N! 隨機訪問 MAC 協(xié)議m在輕負荷時有效率: 單個節(jié)點可以充分利用信道的 帶寬m在重負荷下: 沖突的開銷“輪轉(zhuǎn)式”協(xié)議在兩個方面尋求最佳的解決方案!第6講 數(shù)據(jù)鏈路層之一 6a-31“輪轉(zhuǎn)式” MAC 協(xié)議輪詢（Polling）: r由主結(jié)點“邀請”從結(jié)點依次傳輸rRequest to Send, Clear to Send