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

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

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

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

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

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

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

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

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

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