復習目錄

一、計算機網路基本概念

• 本章節組織結構：基本概念、組件-網路邊緣-網路核心-重點概念（時延-丟包-吞吐量）-協議概念

1.1 認識英特網

概括：由通信鏈路和分組交換機連接巨大數量的端系統構成的巨大轉發網路

構成：

• 主機（host）=端系統（end system）：接入計算機網路的智能設備，個人電腦、智能家電等；又根據功能大致分為客戶（client）、服務器（server）
• 通信鏈路（communication link）：連接網路的線路—物體到物體的一條鏈路構成路徑（path/route）
• 分組交換機（packet switch）：路由器（router）（圓形X表示）和鏈路交換機（switch）（方塊X表示）
• 服務提供商（Internet Service Provider，ISP）：提供接入網路的服務，比如三大運營商等
• 因特網工程任務組（Internet Engineering Task Force，IETF）：負責因特網協議和規范的制訂，制訂檔案統一為RFC（Request For Comment）+編號
• 分組概念（packet）：發送端將長資訊截斷打包
• 傳輸速率（Transmission Rate）：特指將資料搬移到鏈路的轉化速度（bps），注意與傳播速率（Propagation rate）區分

服務：

• 分布式應用程式（distributed application）：基于計算機網路構建的應用，面向網路中的多個物件提供資料交換的應用，如：Web應用，聯網的app等
• API支持：計算機網路包含對應用接入介面的支持，這部分應該被實作在端系統中
• 各種計算機網路—協議（protocol）：定義在兩個或多個通信物體之間交換的報文格式和次序，以及發送和接收以及其他事件應該執行的操作——控制網路資訊接收和發送，比如TCP（Transmission Control Protocol）傳輸控制協議、IP（Internet Protocol）網際協議等

1.2 網路邊緣

• 邊緣路由（edge router）：負責將端系統接入網路的第一個路由器
• 邊緣組：由主機/端系統+接入網構成（家庭組、企業組等）
• 接入技術、物理媒介：略

1.3 網路核心

核心：互聯因特網端系統的分組交換機和通信鏈路構成的網狀結構

需要了解分組轉發網路相關概念

• 分組交換機的輸出快取/佇列（output buffer/queue）：收到資訊先保存在快取中，等轉發埠有空在依次發送
• 存盤-轉發傳輸（store-and-forward transmission）：分組交換機先全部接收一組資訊，存盤，然后在發送端空閑時轉發搬移到下一段鏈路上（產生傳輸延遲（transmission delay）下面講）
• 排隊時延（queuing delay）：由于節點存盤有限，如果不能及時轉發出去，會導致收到的資訊等一段時間才能轉發出去
• 丟包（packet loss）：大概率由于快取滿，導致新接收的包被丟棄
• 轉發表（forwarding table）：收到的資訊中含由目的地資訊，通過查詢轉發表獲取應該轉發到的目的鏈路轉發出去，通過路由選擇協議（routing protocol）自動更新轉發表

電路交換網路方式：通過頻分復用/時分復用技術共享鏈路，固定分配

1.4 ?時延、丟包和吞吐量

端到端時延(d_end-end)：從一個主機發送資訊到另一個主機消耗的時間，由以下4部分組成：

• 節點處理延時（node processing delay）

• 排對延時（queuing delay）

• 傳輸延時（transmission delay）：從節點把資訊搬移到鏈路的時間d_transmission=N*L/R(N是節點個數，L資訊長度、R是傳輸率)

• 傳播延時（propagation delay）：從鏈路一端到另一端的時間（Lenght/C）

• 

• 瓶頸鏈路（bottleneck link）和瓶頸傳輸速率：傳輸速率應該小于節點中最小的傳輸速率，為了避免快取堆積（不確定）

丟包（packet loss）：一次資訊傳輸時中途丟失

• 丟包（packet loss）：大概率由于快取滿，導致新接收的包被丟棄

吞吐量（throughput）：接收到的資訊長度/時間—bps

• 瞬時吞吐量
• 平均吞吐量

1.5 協議層次和服務模型

協議層次(5層因特網協議堆疊)

一個層的所以協議稱為一個協議堆疊（protocol stack）

• 交換機（switch）只需要下兩層協議，不需要尋址
• 路由器（router）需要下面三層協議，需要根據決議IP找到轉發鏈路目標
• 封裝：上層協議的資料被下層附加資訊打包的程序
• 有效載荷欄位（payload field）：除了附加的包頭，即指包體內容

1.6 安全和歷史（略）

二、應用層

2.1 應用層協議原理

相關概念：

• 應用層體系架構（application architecture）：客戶-服務器架構（B/S）、點對點架構（P2P）
• 行程通信：行程作為通信主體，發起通信的作為客戶端，等待連接的作為服務器，通過套接字（socket）這個軟體介面從網路中收發資訊（由4個方面：傳輸率、吞吐量、定時、安全…）
• 尋址：主機地址（IP標識）+行程埠號（port number）
• 容忍丟失應用（loss-tolerant application）：允許一部分丟包
• 帶寬敏感應用（bandwidth-sensitive application）：要求高帶寬，不然無法作業
• 應用層的應用基本上都以TCP作為傳輸層支持（不確定）

應用層協議內容：

• 定義了報文型別（請求/回應)
• 定義了報文語法（每個欄位含有什么）
• 定義了報文的含義（欄位內容如何解讀）
• 報文的回應規則（合適發送，如何發送）

Web是一種B/S應用=HTML標準+瀏覽器+服務器+HTTP協議+…（協議只是應用的一部分）

2.2 ?Web和HTTP協議

超文本傳輸協議（Hypertext Transfer Protocol，HTTP）：定義了Web服務器回傳/Web客戶端請求 內容的方式，以及請求/回應報文的格式，它是一種無狀態協議（stateless protocol），每次收發都不記錄請求者狀態（RFC 1945、RFC 2616）

• 詞匯：web page、web browser、web server、URL、base HTML file
• ?請注意：非持續性連接（non-persistent connection）、持續性連接（persistent connection）、并發連接、流水線模式和HTTP版本
• （待添加）

HTTP報文：

• 請求報文頭部

• 回應報文頭部

• 報文主體和頭部之間用兩個換行隔開

Web快取器（Web cache）/代理服務器（proxy server）：在靠近客戶端建立一個快取服務器，短期內已經訪問過的頁面可以直接從快取服務器獲取，流程如下

1. 建立到快取服務器的TCP連接，發送請求
2. 快取查找有無請求的資源，若有直接回應，節約時間
3. 沒有找到，通過快取服務器（這時叫代理服務器更為恰當）向請求的目標建立TCP連接，轉發請求，獲得目標回應
4. 先在快取中保存一份，然后回應發送到客戶

優點：

• 減少了客戶請求回應時間（特別是對于頻繁請求的熱門資源）
• 降低了帶寬壓力-》內容分發網路（Content Distribution Network，CDN）

流量計算？（不確定）

2.3 FTP和SMTP

• FTP是關于終端間檔案傳輸的協議，服務器用21埠；SMTP是郵件發送的協議，用25埠；SMTP屬于推送協議（push protocol）、HTTP屬于拉取協議（pull protocol）一般服務器采用80埠…

2.4 DNS目錄服務

域名系統（Domain Name System ，DNS）：進行主機名到IP地址的轉化的目錄結構（RFC 1034/RFC 1035）

• 一個由分層的DNS服務器（DNS Server）實作的分布式資料庫
• 使得主機能夠查詢分布式資料庫的應用協議

查詢程序：

1. 對于一個網路應用，需要將主機轉化成IP時，打開DNS客戶端（瀏覽器自動完成）
2. 從URL（這里一Web應用為例）讀取主機名，傳給DNS客戶端
3. 向DNS服務器發送一個包含主機名的查詢請求
4. 收到服務器回復的IP
5. 網路應用向該IP地址+相應埠（Web默認80）發起TCP連接請求

小Tips：

• DSN提供主機別名服務、負載分布服務等

• 它使用的是UDP協議，服務器埠為53

DNS服務器結構

本地DNS服務器（Local DNS Server）：為本地一定范圍內的主機提供查詢范圍——相當于Web快取——即DNS快取機制（DNS caching）

• 主要查詢方式有兩種：遞回查詢（recursive query）、迭代查詢（iterative query）
• 

DNS服務器資源記錄（Resource Record，RR）

• 具體為四元組形式（Name，Value，Type，TTL）
• 根據Type=A（Name標識主機名）、CNAME（主機別名）、NS（域名）、MX（郵件主機名）
• 

2.5 P2P（略）

三、?傳輸層（全重點）

3.1 概述和傳輸層服務

傳輸層為不同主機上的行程提供了邏輯通信（logic communication）；而應用層負責為不同主機之間通信

傳輸層服務：

• 傳輸層的下層網路層中的IP協議盡力而為的互動服務（best-effort delivery service）不能保證資料到達的順序、完整性、設定無法保證送達
• UDP僅能確保資料交付和差錯校驗，不保證資料完好
• TCP提供可靠的資料傳輸（reliable data transfer），并且還有流量控制、序號確認、定時器等機制，TCP確保資料準確有序到達，并且提供擁塞控制服務

3.2 多路復用/分解

• 多路分解（demultiplexing）：傳輸層決議報文欄位定向到指定行程套接字的程序
• 多路復用（multiplexing）：傳輸層從不同套接字接收message報文，封裝向網路層轉發的程序
• 埠（port）：0~1023固定用法，周知埠號（well-know port）；1024~65535供客戶行程使用

3.3 無連接的UDP

應用UDP的優點：

• 通過應用層實作對資料發送更有效的控制
• 無需建立連接，更快
• 無連接狀態
• 分組首部開銷小——UDP首部8位元組，TCP首部20位元組？（不確定）

UDP報文結構：

• 8Byte x 8 = 64bits
• 2Byte 源介面+2Byte 目標介面
• 2Byte 長度+2Byte 檢驗和

校驗和：全部內容求和（注意反卷），然后取反

接收方檢驗時：全部帶校驗和求和結果為全1

3.4 可靠資料傳輸原理（rdt+GBN+SR）

可靠資料傳輸協議（reliable transfer protocol，rdt）：TCP作為其一種實作

接下來通過層層升級解釋可靠資料傳輸協議的實作技術：

• rdt1.0：假設底層通信信道可靠，直接發送和接收資料即可（rdt_send(data):packet=make_pak(data);udt_send(packet)/rdt_rcv(packet):extract(packet,data);deliver_date(data)😉
• rdt2.0：假設為有bit差錯的信道，使用——差錯校驗+接收方發送ACK/NAK+重傳機制（每次發送完需要等接收方發送回ACKorNAK后才能繼續發送，這種模式叫做停等模式（stop-and-wait））
• rdt2.1：考慮發送回的確認包有可能錯誤，導致重傳時不能確定是新發送的包還是重傳包，因此引入組序號機制
• rdt2.2：取消NAK，改為發送上一次成功的ACK和序號
• rdt3.0：添加了丟包的考慮，為防止確認包丟失長時間等待，發送方發送時啟動倒計數定時器（countdown timer）——啟動定時器，中斷回應定時器或者接收成功取消定時器

盡管到rdt3.0已經大致實作了可靠資料傳輸，但是停等模式的性能堪憂，于是進一步探究流水線模式（pipelining）

• 回退N步（Go-Back N，GBN）：N為發送方視窗長度（window-size），因此也叫滑動視窗協議（sliding window protocol）
• 選擇重傳機制（Selective Repeat，SR）：有選擇性的重新傳輸超時的組

GBN：

• 發送方：上層呼叫時，判斷發送視窗是否滿，滿了一般加入發送快取/或者滿了就不允許上層呼叫；收到ACK采用累計確認機制（comulative acknowledgement），該ACK前面的組也確認收到；超時時重發所有沒有被確認的包，每收到一個ACK更新一次定時器；
• 接收方：只維護一個接收口，一次只接收順序到達的一個包；其他情況（亂序，包錯誤）回傳上一次接收成功的包序號ACK，不快取亂序包
• 問題：不適用于開始就出差錯的情況，會導致大量重傳；適用于回傳包有問題情況

SR：

• 發送方：上層呼叫同理；收到ACK將該包標記為確認，不在重發；為每個發送的包設定定時器，超時只重復一個包；
• 接收方：快取亂序包，等到前面的空缺包到達一起遞交；正確收到一個包回傳對應序號的ACK
• 問題：不適用于回傳包有問題情況和亂序較多情況（不確定）

3.5 面向連接的TCP

TCP集以上多種技術于一身：差錯校驗、重傳、累計確認、首部欄位確認號/序號…面向連接——在傳輸資訊前需要建立連接，而且它還屬于

• 全雙工傳輸（full-duplex service）
• 點對點傳輸（point-to-point）
• 需要三路握手（three-ways-handshake）

一些概念：

• 最長報文長度（Maximum Sagement Size，MSS）=最大傳輸單元（Maximum Transmission Unit，MTU）- 40位元組（TCP/IP報文首部）（一般等于1460）
• 序列號（sequence number）：基于發送報文段的第一個位元組在發送快取中的位置
• 捎帶（piggybacked）：在服務器對客戶的請求確認包中捎帶服務器回傳給客戶的資料報文

TCP報文解讀：

三路握手程序：

• Send：SYN=1，seq=client_isn
• Receive:SYN=1，seq=server_isn，ack=client_isn+1
• Send：SYN=0，seq=client_isn，ack=server_isn+1

定時器設定——往返時間估計（不確定，待添加）

特殊功能：

• 超時間隔加倍：當定時器超時，重發包定時器設定為兩倍
• 快速重傳機制：當重復收到3個冗余ACK時，立刻重發該ACK下一個包
• 流量控制（flow control service）：由于接收方快取有限，用以控制發送方流量（更改發送方發送視窗大小）以消除接收方快取溢位的方法
• 擁塞控制（congestion control）：由于IP網路的擁塞而遏制了發送方發送視窗的大小，TCP自動調節發送流量

流量控制具體決議

• 發送方維護一個標識接收方剩余快取的變數為接收視窗（receive window，rwnd）
• 每次接收方回傳ACK時都攜帶自身剩余快取資訊（rwnd=RevBuffer[總快取大小]-（LastByteRevd[最新接收到的資料位置]-LastByteRead[最新被上層讀取的資料位置]）
• 發送方確保發送視窗小于rwnd，即LastByteSent[最新待發送的位置]-LastByteAcked[最新確認的位置]<=rwnd
• 特別的，當rwnd為0時，發送方仍需要發送一個長度為1位元組的報文，目的為了使得接收方回傳ACK說明自己快取是否被清空（部分清空）

3.6 TCP擁塞控制

擁塞控制（congestion control）具體決議：

• 又發送方維護一個變數——擁塞視窗（congestion window，cwnd），對TCP發送方向網路中的發送流量的速率作出限制，和流量控制一起約束，有發送方swnd<=min{rwnd，cwnd}
• TCP確認丟包（一般通過超時、三次冗余ACK）以認為網路擁塞，然后限制速度（降低擁塞視窗大小），相反收到ACK表示網路良好，增長視窗大小——這種特性稱為自計時（self-clocking）
• 擁塞控制三原則：丟包降速、ACK增速、從當前cwnd開始降速，然后逐步試探擁塞情況（不確定）

TCP擁塞控制具體演算法（TCP congestion control algorithm）：

1. 慢啟動：從一個MSS開始，每個ACK增加一個MSS（第一輪一個，第二輪兩個，第三輪四個…每次都會多收到一倍的ACK）；直達丟包發生；記錄此時慢啟動閾值ssthresh=cwnd/2；然后有兩種應對方法——當超時丟包：將cwnd重新設定為1然后重新慢啟動，到達閾值時采用擁塞避免演算法（2）；冗余ACK采用快速恢復方法（3）（這里按題目來）
2. 擁塞避免：丟包后，又一次慢啟動到達閾值時，采用線性增長方法，每個RTT都受到ACK后+1MSS，直到丟包發生，更新閾值重新慢啟動（1）/采用快速恢復（3）
3. 快速恢復：三個冗余ACK后，不重新到1個MSS，而是直接設定為當前cwnd/2+3(記錄的冗余ACK數量)，然后開始線性變化同（2），丟包同上

該擁塞控制特性為線性增-乘性減（Additive-Increase，Multiplicative-decrease，AIMD）

四、?網路層（全重點）

4.1 概述

本章節線路——

網路層服務-構造網路層分組交付的兩種方法-路由器作業原理和網際協議-轉發和路由選擇-路由選擇演算法和協議-廣播和多播

• 轉發：當一個分組到達路由器一個輸入時，將其移到另一個輸出鏈路上的程序
• 路由選擇（routing）：當分組從發送方流向接收方，網路層（所有路由器）決定的該分組應該經過的路徑（最短路選擇，詳情看路由選擇演算法（routing algorithm）
• 轉發表（forwarding table）：由路由器維護的，通過檢索分組目的地首欄位決定輸出鏈路的對照表
• 鏈路交換機（link-layer switch）：實作到鏈路層的交換機，只根據鏈路層資訊轉發，詳見下一章
• 路由器（router）：基于網路層地址實作轉發的設備

網路層服務模型（network service model）：定義了分組在發送與接收端之間的網路層特性

• 確保交付、有交付時延上限、有序分組交付、確保最小帶寬、保證最大延時抖動、安全性等
• 但是很遺憾，最常用的IP協議只能保證盡力而為（best-effort-service）的服務
• 除此之外還有：恒定位元率（Constant Bit Rate，CBR）ATM網路服務，可用位元率（Available Bit Rate，ABR）ATM網路服務這些有保證的服務

網路層和傳輸層差別

• 傳輸層面向不同主機行程通信，而網路層只負責把資料送到對應主機
• 網路層不同時提供有連接和無連接的服務，而傳輸層可以TCP、UDP都能用
• 網路層在核心網路（路由器）中和端系統都有實作，傳輸層只在端系統（主機）

4.2 虛電路和資料報網路

虛電路（Virtual-Circuit，VC）網路（VCN）：有鏈接的網路服務，在發送方和接收發之間維護一條鏈路

• 源主機和目標主機之間的路徑（一系列路由器和鏈路）
• VC號（標識不同路徑不同鏈路）
• 轉發表（記錄一條路徑入VC和出VC號，跨過該路由的每條路徑都需要一組VC對應）

資料報網路（datagram network）：無連接狀態的網路，發送發只負責將含有目標IP地址的datagram包發送給下層輸送到網路中即可，不需要先建立維護一條路徑，會有路由器自動根據轉發表轉發到目標地址

• 轉發表前綴（prefix）匹配-最長前綴匹配原則（loggest prefix matching rule）：將目標地址和轉發表中最長匹配到的前綴做為轉發目標，把分組轉發到對應的鏈路

4.3 路由器作業原理

轉發功能（forwarding function）：組成——輸入/輸出埠（指接收/發送資料的物理介面）、交換結構（將輸入與輸出相連的內部結構）、路由選擇處理器（維護路由選擇表以及連接鏈路狀態和更新路由表的處理器）、以及相應的執行路由選擇協議，回應輸入轉發的軟體——又可分為路由器轉發平面（router forward plane）和路由器控制平面（router control plane）

輸入埠、輸出埠（略）

交換結構

• 經記憶體交換
• 經總線交換
• 經網狀結構交換

一些名詞（不重要）：負責調度（packet schedule）、服務質量保證（quality-of-service guarante）、棄尾（drop tail）策略、主動佇列管理（Active Queue Managerment，AQM）、隨機早期檢測（Random Early Detection，RED）

4.4 網際協議

因特網網路層三大部件：

• IP協議（使用無連接的IP協議提供服務，盡力而為的服務，啥都不保證，需要在傳輸層TCP保證）
• 路由選擇部分
• 網路層差錯控制和資訊報協議，互聯網控制報文協議（ICMP）

IP協議資料報格式

相關概念

• 介面（interface）：物體節點與物理鏈路之間的邊界，IP地址與介面相關聯，而不是和主機相關聯
• 子網（subnet）：具有相同前綴IP的多個相互連接的介面構成一個子網，比如223.1.1.0/24，表示前24為前綴相同的介面組成了223.1.1.0這個網段的子網，后8位全零標識子網，全1表示廣播地址
• 子網掩碼（network mask）：定義子網前綴范圍，如前24為全1，取得一個IP求與運算可得子網前綴，方便匹配
• 無類別域間路由選擇（classless Inter Domain Routing，CIDR）：將子網劃分為如下形式：a.b.c.d/x
• 之前使用的分類編制（classfull addressing）：子網的前綴只能為1，2，3個位元組

網路層接入：

• ??地址塊分配方法
• 動態主機配置
• 網路地址轉換

地址塊分配方法（由大到小逐個分配，詳見書）

動態主機配置協議（Dynamic Host Configuration Protocol，DHCP）：通過一臺DHCP服務器為接入的主機動態分配IP地址的方法（接入的主機可獲得不同的隨機分配的IP或固定IP），使得接入的新主機獲取到IP地址、第一跳路由器、本地DNS服務器地址等，也叫即插即用（plug-and-paly）的協議

1. DHCP服務器發現：由接入主機啟動DHCP客戶端發送DHCP發現報文（DHCP discover message）廣播到目的地址全1地址，源地址標識為全0，通過鏈路交換機/子網路由器廣播
2. DHCP服務器提供：服務器收到發現報文，用一個DHCP提供報文（DHCP offer message）回應，同樣廣播全1地址
3. DHCP請求：客戶選擇一個提供報文，向該服務器發送DHCP請求報文（DHCP request message）
4. DHCP ACK：被選中的服務器用DHCP ACK報文（DHCP ACK message）進行回應，證實其引數

網路地址轉換（Network Address Translation，NAT）：應對IP不夠分配的情況，允許本地子網地址轉換為統一唯一的IP地址共用一個公網IP

• 通過NAT路由器維護一張NAT轉換表（NAT translation table）
• 轉換對應如：10.0.0.1：3445（本地IP：行程埠）《——》138.76.29.7：5001（共用公網IP：隨機系結埠），可隨機分配2¹⁶個埠

ICMP因特網控制報文協議（不重要）、IPv6兼容IPv4

4.5 路由選擇演算法

• 默認路由器（default router）：主機連接的路由器，第一跳路由器（first-loop router）

• 源路由器（source router）：發送方的默認路由器

• 目的路由器（destination router）：接收方的默認路由器

路由選擇問題->最低費用路徑（least-cost path）問題->最短路徑（shortest path）問題

路由選擇問題分類：

• 全域/分散式路由選擇演算法（global/decentralized routing algorithm）-鏈路狀態（Link-State，LS）演算法（全域）/距離向量（Distance-Vector，DV）演算法（分散式）
• 靜態/動態路由選擇演算法（static/dynamic routing algorithm）
• 負載敏感/負載遲鈍（load-sensitive/load-insensitive）

LS演算法和DV演算法詳情見書（內容實在是太多了，比較復雜，有考的概率）

LS演算法對應OSPF（開放最短路經優先協議）（Open Shortest Path First）

DV演算法對應RIP（路由選擇資訊協議）（Routing Information Protocol）

五、鏈路層

5.1 鏈路層概述

鏈路層概念和技術-差錯檢測和糾正-多路訪問鏈路和協議-交換局域網

• 節點（node）：能運行鏈路層協議的任何設備（如主機、路由器、交換機、WiFi接入點）
• 鏈路（link）：沿通信路徑連接兩個節點的通信信道
• 鏈路層幀（frame）：在鏈路層封裝的包

鏈路層提供的服務：

• 成幀（framing）：提供將上層資料添加相關標準封裝的功能
• 鏈路接入：媒體訪問控制協議（Medium Access Control，MAC）協議：規定幀在鏈路上的傳輸規則
• 可靠交付
• 差錯檢驗和糾正技術

鏈路層主體在網路配接器（network adapter）也叫網路介面（network Interface Card NIC）上實作，其核心是鏈路層控制器，實作了許多鏈路層服務（成幀、鏈路層接入、差錯檢測）的專用芯片

5.2 差錯檢測和糾正技術

• 位元級差錯檢測和糾正（bit-level error detection and correction）
• 差錯檢測和糾正位元（Error-Dection and Correction，EDC）：保護位元免受差錯的技術

相關技術

• 奇偶校驗位（parity bit）：奇校驗加上校驗位使得有奇數個1，偶校驗則加上校驗位有偶數個1

• 二維奇偶校驗（two-dimensioned parity）：

• 

• 校驗和：因特網校驗和（Internet checksum）：將k位元整數加起來得到的和作為差錯檢測位（TCP和UDP使用16bit一組反卷求和結果取反作為校驗和，對所有欄位求和（首部和資料段））

• 回圈校驗冗余（Cyclic Redundancy Check，CRC）：也叫多項式編碼（polynomial code）

回圈冗余校驗碼計算方法：

1. 雙方約定一個生成多項式（generaor）——r+1位位元，稱為G（首位一定為1）
2. 發送的資料D后添加r個0
3. 使用D添加0后除以G，使用XOR除法
4. 求得余數R作為CRC位元，和附加在原D后
5. 接收方用收到的D連接R，除以G得0判斷為正確
   

5.3 多路訪問鏈路和協議

點對點鏈路（point-to-point）：由單個發送方和單個接收方組成的通信鏈路（如PPP協議，高級資料鏈路控制（high-level data link control，HDLC）

廣播鏈路（broadcast link）：多個發送方和接收方都連接到相同單一的共享鏈路（涉及多路訪問問題（multiple access problem），相關的多路訪問協議（multiple access protocol）分三類如下

• 信道劃分協議（channel partioning protocol）——時分多路復用（TDM）、頻分多路復用（FDM）、碼分多路復用（CDMA）等
• 隨機接入協議（random access protocol）——ALOHA協議、載波偵聽多路訪問協議（CSMA）
• 輪流協議（taking-turns protocol）——輪詢協議（polling）、令牌傳遞協議（token-pass）

協議共有特點：

• 只有一個使用者，獨占帶寬
• 多個平分
• 分散，不會因為一個節點損害而不能使用
• 簡單，實作簡單

5.4 交換局域網（MAC、交換機）

通過鏈路層尋址和地址決議服務（ARP，將IP地址轉換成鏈路層地址）實作交換局域網

• MAC地址：又叫LAN地址、物理地址（physical address）、長度為6個位元組

• 地址決議服務（Address Resolution Protocol，ARP）：通過輸入目標IP查找在子網中的節點MAC地址，只查詢子網中的MAC地址；主機中維護一張ARP對照表（ARP Table）（IP地址，MAC地址，TTL）

• 通過ARP服務查找MAC程序（通過發送和回傳ARP分組）：

• 1. 網路層傳輸到鏈路層獲取到IP，鏈路層通過該目標IP+廣播MAC地址（全1），廣播到子網所有介面
  2. 目標IP的節點獲取到該請求回傳自身MAC地址，發送一個回應ARP分組
  3. 查詢主機獲取回應得到目標MAC地址，更新ARP表，發送IP資料報
  4. 鏈路層獲取到IP資料報，添加剛付訓取到的MAC地址封裝發送

  MAC目標地址只會在同一子網中，不同子網的目標IP會查詢到邊緣出口路由器的MAC地址

交換機的轉發和過濾：

• 過濾器（filtering）：決定一個幀應該轉發到某個介面還是應該丟棄的功能

• 轉發（forwarding）：決定一個幀應該被導向到哪個介面

• 交換機表（switch table）（MAC地址、介面、時間）基于MAC地址的轉發，三者情況

• 1. 從x介面輸入的包MAC地址查找不到，廣播到所有介面
  2. 查找到為x介面，直接丟棄
  3. 查找到輸入MAC的對應介面為y，從y介面輸出

交換機自學習特性，程序：

1. 表初始為空
2. 對于每個輸入幀，記錄其源MAC地址和介面號，以及輸入時間
3. 一段時間后若沒有該MAC地址訊息，洗掉該MAC對照

優點：

• 消除了碰撞
• 異質的通信鏈路
• 能夠管理

結尾

作者長期更新，如果覺得本文還算不錯的話，請給我一個大大的贊！！！
如果非常贊同這篇文章，請關注我，持續了解更多精彩博文！！！

祝大家期末必勝呀！！！沒有學計算機網路的小伙伴也可以先收藏，說不定以后就學到了，作為知識點手冊也可以的！！！