計算機網(wǎng)絡(luò)自頂向下設(shè)計的讀書筆記

1、1、 數(shù)據(jù)鏈路層服務(wù)1、 數(shù)據(jù)鏈路層的一些術(shù)語/概述(1) 、結(jié)點：主機和路由器1) 鏈路： 連接相鄰結(jié)點的通信信道a. 物理鏈路a) 有線鏈路（wired link）b) 無線鏈路（wireless link）c) 局域網(wǎng)（LANs）b. 數(shù)據(jù)鏈路(2) 、幀（frame）：鏈路層（第二層）數(shù)據(jù)分組，封裝網(wǎng)絡(luò)層數(shù)據(jù)報(3) 數(shù)據(jù)鏈路層負責(zé)實現(xiàn)物理鏈路之間直接相連的相鄰結(jié)點傳送數(shù)據(jù)報2、 鏈路層服務(wù)1 組幀1) 封裝數(shù)據(jù)報構(gòu)成數(shù)據(jù)幀，加首部和尾部2) 幀同步：如何從物理層傳來的比特流識別幀2 鏈路接入1) 如果是共享介質(zhì)，需要解決信道接入（channel access）2) 幀首部中的“MAC

2、”地址，用于標識幀源和目的a. 不同于IP地址3 相鄰結(jié)點間可靠交付/傳輸1) 在低誤碼率的有線鏈路上很少采用（如光纖，某些雙絞線）2) 無線鏈路：wife4 流量控制1) 協(xié)調(diào)相鄰的發(fā)送結(jié)點和接收5 差錯檢測1) 信號衰減和噪音會引起差錯2) 接收端檢測到差錯a. 通知發(fā)送端重傳或者直接丟棄幀6 差錯糾正1) 接收端直接糾正比特拆錯7 全雙工和半雙工通信控制1) 全雙工：鏈路兩端結(jié)點同時雙向傳輸2) 半雙工：鏈路兩端結(jié)點交替雙向傳輸？3、 鏈路層的具體實現(xiàn)1 每個主機或者嗯路由器接口-網(wǎng)卡2 鏈路層在“適配器”（即網(wǎng)絡(luò)接口卡-NIC）中實現(xiàn)或者在一共芯片上實現(xiàn)1) 以太網(wǎng)卡，802.11網(wǎng)卡

3、；以太網(wǎng)芯片組2) 實現(xiàn)鏈路層和物理層3 鏈接主機的系統(tǒng)總線4 由硬件、軟件于固件組成2、 差錯編碼1、 差錯檢測的基本原理2、 差錯編碼的檢錯能力1 差錯編碼可分為檢錯碼和糾錯碼2 對于檢錯碼，如果編碼集的漢明距離ds = r + 1，則該差錯編碼可以檢測r位的差錯1) 漢明距離：兩個等長字符串之間的漢明距離是兩個字符串對應(yīng)位置的不同字符的個數(shù)。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數(shù)2) 編碼集的漢明距離：任意兩個數(shù)的漢明距離的最小值3) 比如由c1與c2，c1與c2之間漢明編碼一定大于r+1，如果c1錯了r位，那c1也變成不了c2，因此錯誤的那一個一定會被檢測

4、出來的3 對于糾錯碼，如果編碼集的漢明距離ds = 2*r + 1,則該差錯編碼可以糾正r位的差錯1) 將無效的碼字糾錯成離它最近的碼字4 奇偶校驗碼5 CheckSum發(fā)送端1) 將“數(shù)據(jù)”（校驗內(nèi)容）劃分位為16位的二進制“整數(shù)”序列2) 求和（sum）：補碼求和（最高位進位的“1”，返回最低位繼續(xù)加）3) 校驗和（Checksum）：sum的反碼4) 放入分組（UDP、TCP、IP）的校驗和字段接收端1) 與發(fā)送端相同算法計算2) 計算得到的“checksum”a) 全為0（或全1）：無措b) 否則有錯6 循環(huán)冗余校驗碼（CRC）1) 檢錯能力更強大的差錯編碼2) 將數(shù)據(jù)比特，D,視為一

5、個二進制數(shù)3) 選擇一個r+1位的比特模式（生成比特模式），G4) 目標：選擇r位的CRC比特，R，滿足a. 剛好可以被G整出（模2）b. 接收端檢錯：利用G除，余式全0，無措；否則，有錯！c. 可以檢錯所有突發(fā)長度小于r+1的差錯5) 廣泛應(yīng)用于實際網(wǎng)絡(luò)（以太網(wǎng)，802.11wife，ATM0）3、 MAC：（multiple access control protocol）多路訪問控制協(xié)議1、 兩類電路：1 點對點電路1) 撥號接入的PPP2) 以太網(wǎng)交換機于主機間的點對點鏈路2 廣播電路(共享介質(zhì))1) 早期的總線以太網(wǎng)2) 802.11無線局域網(wǎng)3) HFC的上行鏈路2、 解決問題-1

6、 單一共享廣播信道2 兩個或者兩個以上結(jié)點同時傳輸：干擾1) 沖突a. 結(jié)點同時接收兩個或多個信號-接收失敗3 MAC協(xié)議1) 采用分布式算法決定結(jié)點如何共享信道，即決策結(jié)點合可以傳輸數(shù)據(jù)2) 必須基于信道本身，通信信道共享協(xié)調(diào)信息！a. 無帶外信道用于協(xié)調(diào)4 理想的MAC協(xié)議1) 給定：速率位R bps的廣播信道2) 期望：a. 當(dāng)只有一個結(jié)點希望傳輸數(shù)據(jù)時，它可以以速度R發(fā)送b. 當(dāng)有M個結(jié)點期望發(fā)送數(shù)據(jù)時，每個結(jié)點平均以速度R/M速度發(fā)送c. 完全分散控制a) 無需特定結(jié)點協(xié)調(diào)b) 無需時鐘、時隙同步d. 簡單5 MAC協(xié)議分類1) 三大類a. 信道劃分MAC協(xié)議a) 多路復(fù)用技術(shù)b)

7、TDMA，F(xiàn)DMA，CDMA，WDMA等c) FDMAi. 信道頻譜劃分未若干頻帶ii. 每個站點分配一個固定頻帶iii. 無傳輸頻帶空閑d) TDMAi. “周期性”接入信道ii. 每個站點在每個周期、占用固定長度的時隙（長度=每組傳輸時間）iii. 未使用時隙空閑e) 如果網(wǎng)絡(luò)負載重，利用率大f) 如果網(wǎng)絡(luò)負載輕，利用率小b. 隨機訪問（random access）MAC協(xié)議a) 信道不劃分，允許沖突b) 當(dāng)有結(jié)點要發(fā)送分組時:i. 利用信道的全部速率R發(fā)送分組ii. 沒有實現(xiàn)的結(jié)點間協(xié)調(diào)c) 采用沖突“恢復(fù)”機制i. 如何檢測沖突ii. 如何從沖突中恢復(fù)（eg 通過延遲重傳）d) 典型的

8、隨機訪問MAC協(xié)議i. 時隙（sloted）ALOHA協(xié)議i) 假定a. 所有幀大小相同b. 時間被劃分為等長的時隙（每個時隙可以傳輸一個幀）c. 結(jié)點只能在時隙開始時刻發(fā)送幀d. 結(jié)點間時鐘同步e. 如果有2個或2個以上結(jié)點在同一時隙發(fā)送幀，結(jié)點檢測到?jīng)_突ii) 運行a. 當(dāng)結(jié)點有新的幀時，在下一個時隙發(fā)送b. 如果無沖突：該結(jié)點可以在下一個時隙繼續(xù)發(fā)送新的幀c. 如果沖突：該結(jié)點在下一個時隙以概率p重傳該幀，知道成功iii) 優(yōu)點a. 單個結(jié)點活動時，可以連續(xù)以信道全部速率傳輸速率b. 高度分散化：只需同步時隙c. 簡單缺點a. 沖突、浪費時隙b. 空閑時隙c. 結(jié)點也許遠小于分組傳輸時間

9、檢測到?jīng)_突d. 時鐘同步效率ii. ALOHAi) 非時隙（純）Aloha：更加簡單，無需同步ii) 當(dāng)有新的數(shù)據(jù)幀生成時a. 立即發(fā)送iii) 沖突可能性增大效率iii. CSMA CSMA/CD CSMA/CAi) CSMA（載波監(jiān)聽多路訪問協(xié)議：carrier sense multiple access）a. 發(fā)送幀之前，監(jiān)聽信道（載波）-判斷是否有其他數(shù)據(jù)信道空閑：發(fā)送完整幀信道忙：推遲發(fā)送1- -堅持CSMA非堅持CSMAP- -堅持CSMAb. 沖突仍然有可能發(fā)生：信號傳播延遲c. 繼續(xù)發(fā)送沖突幀：浪費信道資源ii) CSMA/CD CSMA with collision detectiona. 短時間可以檢測沖突b. 沖突后傳輸終止，減少信道浪費c. 沖突檢測a) 有限局域網(wǎng)易于實現(xiàn)：測量信號強度，比較發(fā)射信號于接收信號b) 無線局域網(wǎng)很難實現(xiàn)：接收信號強度淹沒在本 地發(fā)射信號強度下c) 邊發(fā)邊聽，不發(fā)不聽c. 輪轉(zhuǎn)（“taking turns”）MAC協(xié)議a) 結(jié)點輪流使用信道b) 輪詢（polling）：i. 主結(jié)點輪流“邀請”從屬結(jié)點發(fā)送數(shù)據(jù)ii. 典型運用：i) 啞從屬設(shè)備ii) . 輪詢開銷iii) 等待延遲iv) 單點故障問題（主結(jié)點有問題） c)