國科大計算機(jī)網(wǎng)絡(luò)復(fù)習(xí)整理筆記-創(chuàng)新互聯(lián)

1. 互聯(lián)網(wǎng)體系結(jié)構(gòu)可自下而上分為鏈路層，網(wǎng)絡(luò)層，傳輸層和應(yīng)用層，請簡述各層主要功能，與代表性協(xié)議，以及該分層模型的優(yōu)缺點(diǎn)。

1. 數(shù)據(jù)鏈路層
	功能：向該層用戶提供透明的和可靠的數(shù)據(jù)傳送基本服務(wù)，進(jìn)行幀編碼和差錯控制，使之對網(wǎng)絡(luò)層表現(xiàn)為無差錯的線路（解決分組在一個網(wǎng)絡(luò)（或一個鏈路）上傳輸?shù)膯栴}）
	代表協(xié)議：
		P2P協(xié)議
		以太網(wǎng)協(xié)議

2. 網(wǎng)絡(luò)層
	功能：在數(shù)據(jù)鏈路層提供的兩個相鄰端點(diǎn)之間的數(shù)據(jù)幀的傳送功能上，進(jìn)一步管理網(wǎng)絡(luò)中的數(shù)據(jù)通信，將數(shù)據(jù)設(shè)法從源端經(jīng)過若干個中間節(jié)點(diǎn)傳送到目的端，從而向傳輸層提供最基本的端到端的數(shù)據(jù)傳送服務(wù)。（負(fù)責(zé)為分組交換網(wǎng)上的不同主機(jī)提供通信服務(wù)，解決分組在多個網(wǎng)絡(luò)上傳輸（路由）的問題）
	代表協(xié)議：
		IP
		ARP（地址解析協(xié)議）
		ICMP（網(wǎng)際控制報文協(xié)議）
		路由選擇協(xié)議
		NAT（網(wǎng)絡(luò)地址轉(zhuǎn)換協(xié)議）
		
3. 傳輸層
	功能：主要負(fù)責(zé)向兩個主機(jī)中進(jìn)程之間的通信提供服務(wù)，提供差錯控制和流量控制
	代表協(xié)議：
		TCP
		UDP

4. 應(yīng)用層
	功能：負(fù)責(zé)通過應(yīng)用進(jìn)程間的交互來完成特定網(wǎng)絡(luò)應(yīng)用的任務(wù)。（為應(yīng)用進(jìn)程提供服務(wù)）
	代表協(xié)議：
		FTP
		DNS
		HTTP
		SMTP

2. 交換機(jī)/路由器將待處理的數(shù)據(jù)包放到緩沖隊列中， 緩沖隊列的大小對設(shè)備的轉(zhuǎn)發(fā)性能有很大的影響，請簡述隊列過大或過小對傳輸流的性能影響。 RED 機(jī)制可以緩解隊列過大帶來的性能問題， 請簡述該機(jī)制的運(yùn)行過程。

隊列大小的影響：
	緩沖區(qū)太小，會導(dǎo)致丟包率過高，數(shù)據(jù)鏈路利用率低，TCP傳輸效率低
	緩沖區(qū)太大，會導(dǎo)致網(wǎng)絡(luò)擁塞時，數(shù)據(jù)包轉(zhuǎn)發(fā)時延過大

RED（Random early detection）隨機(jī)早期檢測
	在RED中，為緩存隊列都設(shè)置了一個最小閾值和大閾值，當(dāng)收到數(shù)據(jù)包時：
		- 若隊列長度小于最小閾值，直接加入緩存隊列
		- 若隊列長度大于大閾值，直接丟棄數(shù)據(jù)包
		- 若隊列長度位于兩者之間，開始按一定概率丟棄數(shù)據(jù)包。隊列越長，丟棄概率越高

3. OSPF 路由協(xié)議的核心是鏈路狀態(tài)機(jī)制，請簡述該協(xié)議的運(yùn)行原理，拓?fù)渥儎雍蟮氖諗窟^程以及如何拓展到規(guī)模更大的網(wǎng)絡(luò)環(huán)境的方法。

第七個實(shí)驗mospf，做過自然懂嗷

運(yùn)行原理：
	OSPF設(shè)備向外發(fā)送hello包，與其他使用相同協(xié)議的設(shè)備建立鄰居關(guān)系
	互相發(fā)送LSA（鏈路狀態(tài)通告）相互通告路由，形成LSDB（鏈路狀態(tài)數(shù)據(jù)庫）
	基于LSDB通過SPF算法，計算通向每個目的網(wǎng)絡(luò)的最佳路徑后，放入路由表。
	
收斂過程：
	進(jìn)行LSA的泛洪
	收集泛洪的LSA集合，進(jìn)行LSDB的組建
	基于LSDB用SPF算法得到一顆以自己為“根”覆蓋全網(wǎng)的無環(huán)的樹
	
擴(kuò)展方法：
	將一個自治系統(tǒng)再劃分為若干個更小的范圍，叫區(qū)域，使更新過程收斂更快

4. TCP 擁塞控制機(jī)制，包括慢啟動、擁塞避免、快速重傳、快速恢復(fù)等功能，這些功能共同完成了數(shù)據(jù)流的高可靠和高性能傳輸請簡述每種功能的原理和設(shè)計目標(biāo)。

定義

5. 請簡述“在瀏覽器中輸入網(wǎng)址到獲取網(wǎng)頁內(nèi)容” 這段時間內(nèi)發(fā)生的操作

見2017.1

6. 請簡述基于 Trie 樹的 Ipv4 路由表查找算法的時間和空間復(fù)雜度以及基于 Ipv6 的路由表的查找算法的優(yōu)化方法。（今年ppt沒這玩意，應(yīng)該不考吧）

復(fù)雜度：
	假設(shè)查找字符串長度為n，則時間復(fù)雜度為O(n)
	字典樹每個節(jié)點(diǎn)都需要使用一個數(shù)組來存儲子節(jié)點(diǎn)的指針即便實(shí)際只有兩三個子節(jié)點(diǎn)，但依然需要一個完整大小的數(shù)組。所以，空間復(fù)雜度較高O(26^n)
	
基于Ipv6的路由表的查找算法：基于前綴hash表的二分搜索

優(yōu)化方法：
	降低時間復(fù)雜度: Sail
	降低空間復(fù)雜度: DxR
	在時空復(fù)雜性上進(jìn)行折衷考慮和優(yōu)化: Poptrie

7. 簡述區(qū)塊鏈上數(shù)據(jù)不可偽造、不可抵賴、難以刪除和難以篡改的技術(shù)原理，區(qū)塊鏈的共識算法的作用是什么？請舉出現(xiàn)實(shí)生活中用區(qū)塊鏈技術(shù)解決實(shí)際問題的一個實(shí)例，并說明區(qū)塊鏈解決了其中的什么問題。 區(qū)塊鏈與分布式數(shù)據(jù)庫的異同？

見2020.11

8. BBR 是 Google 提出的一種擁塞控制算法，其核心思想是測量最小 RTT 和瓶頸鏈路的可用帶寬，請簡述為什么最小 RTT 和瓶頸鏈路的可用帶寬不能同時測得，以及如何才能較為準(zhǔn)確地測量這兩個值。

原因：
	要測量大帶寬，就要把瓶頸鏈路填滿，此時buffer中有一定的數(shù)據(jù)包，自然測不了最小RTT
	要測量最低延遲，就要保證buffer為空，網(wǎng)絡(luò)中的數(shù)據(jù)包越少越好，這也與瓶頸鏈路帶寬的測量條件相悖

如何準(zhǔn)確測量：
	 針對測不準(zhǔn)的問題，在論文中BBR算法采?的?案是，交替測量帶寬和延遲，??段時間內(nèi)的帶寬極?值和延遲極?值作為估計值，動態(tài)更新測量值，最終控制發(fā)送速率，避免?絡(luò)擁塞。

9. 數(shù)據(jù)包負(fù)載均衡和數(shù)據(jù)流復(fù)制均衡的優(yōu)劣

見2020.8

10. CDN 依賴于 DNS 實(shí)現(xiàn)用戶到服務(wù)器的映射，假設(shè)使用傳統(tǒng) DNS 協(xié)議，用戶側(cè)配置公用的 DNS 服務(wù)器（如 8.8.8.8）和使用運(yùn)營商自動配置的本地 DNS 服務(wù)器會對這種映射造成什么影響？如何緩解這種影響？

影響：
	在DNS查詢過程中，權(quán)威服務(wù)器接收請求的時候，只能得到本地DNS的IP，并不知道客戶端IP。如果本地DNS設(shè)置不當(dāng)，可能會誤判用戶的位置，將用戶誤導(dǎo)到錯誤的CDN緩存節(jié)點(diǎn)，造成加速效果差的問題。

緩解：
	可以利用end-user mapping的技術(shù)，通過客戶端IP地址的前綴，來對客戶端進(jìn)行表示識別。

11. NDN 等未來互聯(lián)網(wǎng)體系結(jié)構(gòu)試圖改變 TCP/IP 協(xié)議的哪些方面，為什么這些新型的互聯(lián)網(wǎng)體系結(jié)構(gòu)部署比較困難？

改變：
	可拓展性：在現(xiàn)有互聯(lián)網(wǎng)體系結(jié)構(gòu)中，只能通過不斷地增加硬件設(shè)備進(jìn)行拓展
	動態(tài)性：使網(wǎng)絡(luò)中身份和位置分離，增加可移動性
	安全可控性：構(gòu)建面向服務(wù)和數(shù)據(jù)的安全架構(gòu)，從源頭上限制網(wǎng)絡(luò)攻擊行為的發(fā)生
	
部署困難原因：
	網(wǎng)絡(luò)規(guī)模太大，不易統(tǒng)一部署
	且過去的網(wǎng)絡(luò)設(shè)備在設(shè)計之初并沒有考慮到這些問題，無法直接應(yīng)用這些架構(gòu)

1. 最小生成樹機(jī)制能夠在有環(huán)的物理網(wǎng)絡(luò)中構(gòu)造出一個無環(huán)的樹狀邏輯拓?fù)洌诒ＷC網(wǎng)絡(luò)連通性的同時避免廣播風(fēng)暴。當(dāng)網(wǎng)絡(luò)是靜態(tài)時，即不存在節(jié)點(diǎn)/鏈路的加入和刪除，網(wǎng)絡(luò)對應(yīng)的最小生成樹拓?fù)涫欠袷俏ㄒ坏?？簡述或舉例說明

構(gòu)造的最小生成樹是可能不唯一，但是最小生成樹的權(quán)值是唯一的。當(dāng)無向圖中存在相同權(quán)值的邊，并且該邊的權(quán)值小于最小生成樹中邊集的大權(quán)值，則一定存在多個最小生成樹。（自由發(fā)揮）

2. 考慮下圖中的網(wǎng)絡(luò)拓?fù)?，每條邊上的數(shù)字代表對應(yīng)鏈路的代價，使用距離向量的方法進(jìn)行網(wǎng)絡(luò)路由選擇，當(dāng)前節(jié)點(diǎn)A和C的路由表項分別如下兩個子表所示，當(dāng)兩個節(jié)點(diǎn)分別收到節(jié)點(diǎn)B的距離向量信息（A:2，B:0，C:4，D:2，E:1，F(xiàn):3）后，試更新兩個節(jié)點(diǎn)的路由表項。

和2016.10差不多，簡簡單單，自由發(fā)揮！

貌似就更新了C的ADF三項，cost分別為6，6，7，下一跳均為B（自行驗證啊自行驗證）

3. 基于路由轉(zhuǎn)發(fā)表的表項進(jìn)行最長前綴，確定下一跳轉(zhuǎn)發(fā)路徑，是路由查找轉(zhuǎn)發(fā)的基本動作。Trie查找是主要路由查找算法之一，下圖（a）是路由表的示例，圖（b）是對應(yīng)的trie數(shù)據(jù)結(jié)構(gòu)。請描述IPV4路由查找中Trie查找過程。分析時間復(fù)雜度和空間復(fù)雜度。

查找過程：
    1. 從根結(jié)點(diǎn)開始一次搜索；
    2. 取得要查找關(guān)鍵詞的第一個字符，并根據(jù)該字符轉(zhuǎn)到對應(yīng)的子樹進(jìn)行檢索
    3. 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個字符,并進(jìn)一步選擇對應(yīng)的子樹進(jìn)行檢索。
    4. 迭代過程……
    5. 在某個結(jié)點(diǎn)處，關(guān)鍵詞的所有字符已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找

時間復(fù)雜度：O(n) n為路由長度
空間復(fù)雜度：O(1) 無額外空間

4. TCP通過AIMD（加性增，乘性減）機(jī)制來探測可用帶寬和保障競爭流間的公平性。只考慮AIMD機(jī)制，試在如下圖（a）中畫出一個TCP流的擁塞窗口隨時間變化的形狀，并說明該形狀的變化周期。對于兩個競爭流，從如下圖（b）中的起始點(diǎn)出發(fā)，在圖中通信兩個競爭流的發(fā)送速率收斂到最優(yōu)點(diǎn)過程中的變化曲線。

答案參考下面這個圖：不知道為啥的再去看看TCP機(jī)制

5. TCP傳輸協(xié)議中，發(fā)送的字節(jié)數(shù)與吞吐及RTT的關(guān)系如下圖所示。假設(shè)路徑的傳輸時延為RTT，瓶頸鏈路帶寬為BW，瓶頸鏈路處的隊列長度為Q，則（1）D1, Slope1, Slope2, S1, S2分別為多少？（2）BBR根據(jù)傳播時延與瓶頸鏈路帶寬的乘積設(shè)置擁塞窗口，如何測得傳播時延RTT，以及瓶頸鏈路帶寬BW？

（1）D1 = RTT; Slope1 = ?; slope2 = 1 / RTT; S1 = BW * RTT; S2 = BW * RTT + Q


（2）前面有，略

6. 假設(shè)不使用EDNS，當(dāng)客戶端使用Google：8:8:8:8 等公共DNS解析服務(wù)器進(jìn)行內(nèi)容訪問時，CDN有可能會給用戶分配的CDN服務(wù)器離客戶端距離較遠(yuǎn)，原因是什么？EDNS為什么能協(xié)助解決這個問題？Google的8:8:8:8使用Anycast技術(shù)也能在一定程度上緩解該問題。請問原理是什么？

（1）CDN的加速資源是跟域名綁定的，公共DNS由于結(jié)點(diǎn)數(shù)有限，可能經(jīng)常離用戶很遠(yuǎn)
原理：尋找CDN是由DNS服務(wù)器去查詢的，因此尋找CDN的過程其實(shí)并不知道用戶地址，如果是本地DNS則可以找到較近的CDN服務(wù)器，若使用公用DNS則可能不能獲取到較近的CDN資源，影響用戶感知體驗。

（2）EDNS根據(jù)用戶請求來對同一域名作出相應(yīng)的不同解析，允許DNS resolver傳遞用戶的ip地址給權(quán)威DNS服務(wù)器以進(jìn)行精確調(diào)度

（3）Anycast則允許客戶端向一組目標(biāo)服務(wù)器發(fā)送數(shù)據(jù)，而這組服務(wù)器中最終處理數(shù)據(jù)的服務(wù)器是由路由系統(tǒng)選擇“最近”服務(wù)器。

7. 什么是鏈路帶寬，可用帶寬？

見2016.6

8. 數(shù)據(jù)中心網(wǎng)絡(luò)問題：
   ECMP是如何實(shí)現(xiàn)流級別的負(fù)載均衡的？
   流級別負(fù)載均衡和數(shù)據(jù)包級別的負(fù)載均衡相比，劣勢是什么？
   基于ECN的擁塞控制在數(shù)據(jù)中心網(wǎng)絡(luò)中廣泛使用，簡述其原理，以及為什么能緩解TCP Incast問題。

（1）當(dāng)路由器發(fā)現(xiàn)同一目的地址出現(xiàn)多個最優(yōu)路徑時，會更新路由表，為此目的地址添加多條規(guī)則，對應(yīng)于多個下一跳，可同時利用這些路徑轉(zhuǎn)發(fā)數(shù)據(jù)，增加帶寬。

（2）ECMP對于流大小相差不多的情況效果更好，而對于流大小差異較大，特別大的數(shù)據(jù)流無論選擇哪條路徑都容易造成擁塞

補(bǔ)充：
	優(yōu)勢：數(shù)據(jù)包級別的負(fù)載均衡需要對每一個數(shù)據(jù)包進(jìn)行查表操作，因此轉(zhuǎn)發(fā)效率較低；而流級別負(fù)載均衡轉(zhuǎn)發(fā)效率更高
	劣勢：對于長短流差距較大的情況，流級別負(fù)載均衡難以達(dá)到預(yù)期效果
	
（3）基于的丟包反饋、路徑延時反饋、顯示反饋等信息進(jìn)行擁塞窗口調(diào)節(jié)。
交換機(jī)作為集中控制器計算所有流的平均窗口值A(chǔ)VG，通過顯示反饋給發(fā)送端，發(fā)送端統(tǒng)一將發(fā)送窗口調(diào)整為AVG大小來公平的分配帶寬。

補(bǔ)充：
	具體來說，在DCTCP方法中，在交換機(jī)處有一個閾值K，若數(shù)據(jù)包到達(dá)時，隊列占用量大于K，則標(biāo)記該數(shù)據(jù)包。當(dāng)receiver接收到帶有標(biāo)記的數(shù)據(jù)包后，返回帶有ECN標(biāo)記的ACK給發(fā)送端，發(fā)送端以此調(diào)節(jié)擁塞窗口的大小。

9. 未來互聯(lián)網(wǎng)體系結(jié)構(gòu)NDN、SOFIA、MobilityFirst等強(qiáng)調(diào)名字Name和地址Address的分離，請問名字與地址分離解決什么問題？與TCP\IP體系結(jié)構(gòu)不同，NDN是接收端驅(qū)動的，即接收端發(fā)送Interest數(shù)據(jù)包，發(fā)送端收到Interest數(shù)據(jù)包后才回復(fù)Data，且Data沿著Interest數(shù)據(jù)包的反向路徑發(fā)送給接收端，這樣做的好處與劣勢是什么

名字和地址分離是支持移動性的關(guān)鍵

優(yōu)勢：
	不存在身份與地址的綁定，支持移動性
	安全性和可拓展性增強(qiáng)
	減少冗余傳輸，節(jié)省帶寬
	
劣勢：
	名字不定長，在路由表中難查找
	網(wǎng)絡(luò)設(shè)備的實(shí)現(xiàn)和維護(hù)復(fù)雜

10. 非對稱加密相比于對稱加密的優(yōu)劣？

見2016.3

11. 簡述區(qū)塊鏈上數(shù)據(jù)不可偽造、不可抵賴、難以刪除和難以篡改的技術(shù)原理？
    區(qū)塊鏈的共識算法的作用是什么？
    請描述一個區(qū)塊鏈應(yīng)用場景，并論述區(qū)塊鏈技術(shù)主要解決了場景里面的什么問題，是如何解決的？
    區(qū)塊鏈與分布式數(shù)據(jù)庫的異同？

區(qū)塊鏈原理:
	單點(diǎn)出塊：指定一個節(jié)點(diǎn)生成賬本
	廣播機(jī)制：將生成的賬本廣播給所有節(jié)點(diǎn)
	交叉驗證：全網(wǎng)參與，協(xié)作完成交易驗證
	共同存儲：分布式記賬，不依賴單個中心

共識算法作用：確保分布式系統(tǒng)的一致性，保證區(qū)塊信息達(dá)成全網(wǎng)的一致共識

以國家法定數(shù)字貨幣業(yè)務(wù)場景作為例，闡述問題與解決方法
	可編程的交易過程解決了精確可控的貨幣政策問題
	扁平化架構(gòu)解決了擴(kuò)大流通范圍取代紙幣的問題
	共同記賬解決了高效便捷的跨境支付清算問題

不同點(diǎn)
	區(qū)塊鏈只能進(jìn)行查和插，分布式數(shù)據(jù)庫可以進(jìn)行增刪改查
	區(qū)塊鏈每個節(jié)點(diǎn)通常保存全量數(shù)據(jù)，分布式數(shù)據(jù)庫一般只保存部分
	區(qū)塊鏈強(qiáng)調(diào)參與者平等、共享，公開透明、共建，分布式數(shù)據(jù)具有單一擁有者
	區(qū)塊鏈節(jié)點(diǎn)間協(xié)作不需要相互信任，分布式數(shù)據(jù)庫節(jié)點(diǎn)間的協(xié)作建立在相互信任的基礎(chǔ)上
	區(qū)塊鏈容錯機(jī)制好，分布式數(shù)據(jù)庫容錯能力低
	
相同點(diǎn)：
	共識機(jī)制：一致性控制 — 共識機(jī)制
	存儲機(jī)制：數(shù)據(jù)庫日志 — 賬本
	智能合約：智能合約 — 存儲過程

鏈技術(shù)主要解決了場景里面的什么問題，是如何解決的？
區(qū)塊鏈與分布式數(shù)據(jù)庫的異同？

區(qū)塊鏈原理:
	單點(diǎn)出塊：指定一個節(jié)點(diǎn)生成賬本
	廣播機(jī)制：將生成的賬本廣播給所有節(jié)點(diǎn)
	交叉驗證：全網(wǎng)參與，協(xié)作完成交易驗證
	共同存儲：分布式記賬，不依賴單個中心

共識算法作用：確保分布式系統(tǒng)的一致性，保證區(qū)塊信息達(dá)成全網(wǎng)的一致共識

以國家法定數(shù)字貨幣業(yè)務(wù)場景作為例，闡述問題與解決方法
	可編程的交易過程解決了精確可控的貨幣政策問題
	扁平化架構(gòu)解決了擴(kuò)大流通范圍取代紙幣的問題
	共同記賬解決了高效便捷的跨境支付清算問題

不同點(diǎn)
	區(qū)塊鏈只能進(jìn)行查和插，分布式數(shù)據(jù)庫可以進(jìn)行增刪改查
	區(qū)塊鏈每個節(jié)點(diǎn)通常保存全量數(shù)據(jù)，分布式數(shù)據(jù)庫一般只保存部分
	區(qū)塊鏈強(qiáng)調(diào)參與者平等、共享，公開透明、共建，分布式數(shù)據(jù)具有單一擁有者
	區(qū)塊鏈節(jié)點(diǎn)間協(xié)作不需要相互信任，分布式數(shù)據(jù)庫節(jié)點(diǎn)間的協(xié)作建立在相互信任的基礎(chǔ)上
	區(qū)塊鏈容錯機(jī)制好，分布式數(shù)據(jù)庫容錯能力低
	
相同點(diǎn)：
	共識機(jī)制：一致性控制 — 共識機(jī)制
	存儲機(jī)制：數(shù)據(jù)庫日志 — 賬本
	智能合約：智能合約 — 存儲過程

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：國科大計算機(jī)網(wǎng)絡(luò)復(fù)習(xí)整理筆記-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article38/djhcsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、App開發(fā)、網(wǎng)站收錄、App設(shè)計、用戶體驗、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)