计算机网络核心知识（中）
生活随笔
收集整理的這篇文章主要介紹了
计算机网络核心知识（中）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
前言
轉載請聲明轉載并標明本博客鏈接。
(1) 毒性逆轉
(2) 乒乓環路
(3) TOS
(4) 網絡前綴聚合
(5) 滑動窗口協議
上面的是還未搞明白的知識點。
文章目錄
- 前言
- 5 網絡層（上)
- 5.1 網絡層服務
- 網絡層核心功能-轉發與路由
- 網絡層核心功能-連接建立
- 網絡層服務模型
- 5.2 虛電路網絡與數據報網絡
- 5.2.1 虛電路網絡
- 連接服務與無連接服務
- 虛電路(Virtual circuits)
- VC的具體實現
- VC轉發表
- 虛電路信令協議(signaling protocols)
- 5.2.2 數據報網絡
- 數據報轉發表
- 最長前綴匹配優先
- 5.2.3 數據報網絡與VC網絡的對比
- 5.3 IPv4協議
- 5.3.1 IP協議（1）-IP數據報
- IP數據報(分組)格式
- 5.3.2 IP協議（2）-IP分片
- 最大傳輸單元(MTU)
- IP分片與重組
- IP分組格式
- IP分片過程
- 5.3.3 IP協議（3）-IP編址
- IP編址(addressing)
- IP子網（Subnets）
- 5.3.4 IP協議（4）-有類IP地址
- 有類IP地址
- 5.3.5 IP協議（4）-IP子網劃分與子網掩碼
- 如何進行子網劃分(Subnetting)？
- 子網劃分
- 子網掩碼的應用
- 6 網絡層（中)
- 6.1 CIDR與路由聚合
- CIDR與路由聚合的作用
- 路由聚合
- 6.2 DHCP協議
- 6.3 網絡地址轉換(NAT)
- 6.3.1 NAT的實現
- 6.3.2 NAT穿透問題
- 6.4 互聯網控制報文協議(ICMP)
- 6.4.1 ICMP報文的格式
- 6.4.2 ICMP差錯報告報文數據封裝
- 6.4.3 ICMP的應用舉例：Traceroute
- 6.5 IPv6簡介
- 6.5.1 IPv6的研發動機
- 6.5.2 IPv6數據報格式
- 6.5.3 其他改變 vs IPv4
- 6.5.4 IPv6地址表示形式
- 6.5.5 IPv6基本地址類型
- 6.5.6 IPv4向IPv6過渡
- 6.6 典例講解
- 7 網絡層（下）
- 7.1 路由算法概述
- 7.2 鏈路狀態路由算法
- 7.2.1 Dijkstra 算法
- 7.3 距離向量路由算法(1)
- 7.4 距離向量路由算法（2）
- 7.4.1 距離向量DV: 無窮計數問題
- 7.5 層次路由
- 7.5.1 研發層次路由的動機
- 7.5.2 層次路由詳述
- 互連的AS
- 自治系統間(Inter-AS)路由任務
- 舉例說明層次路由
- 7.6 RIP協議
- 7.6.1 AS內部路由
- 7.6.2 RIP
- 7.7 OSPF協議簡介
- 7.7.1 OSPF優點(RIP不具備)
- 7.7.2 分層的OSPF
- 7.8 BGP協議簡介
- 7.8.1 BGP基礎
- 7.8.2 BGP基礎: 分發路徑信息
- 7.8.3 路徑屬性與BGP路由（route）
- 7.8.4 BGP路由選擇
- 7.8.5 BGP路由選擇策略舉例
- 7.8.6 為什么采用不同的AS內與AS間路由協議?
- 8 數據鏈路層
- 8.1 數據鏈路層服務
- 8.1.1 概述
- 8.1.2 鏈路層服務
- 8.1.3 鏈路層的具體實現？
- 8.1.4 網卡間通信
- 8.2 差錯編碼
- 8.2.1 差錯編碼的檢錯能力
- 8.2.2 奇偶校驗碼
- 8.2.3 Internet校驗和(Checksum)
- 8.2.4 循環冗余校驗碼(CRC)
- 8.3 多路訪問控制(MAC)協議
- 8.3.1 理想MAC協議
- 8.3.2 MAC協議分類
- 8.3.3 信道劃分MAC協議
- TDMA
- FDMA
- 8.3.5 隨機訪問MAC協議
- 時隙ALOHA協議 (S-ALOHA)
- ALOHA協議
- CSMA協議
- CSMA/CD協議
- 8.3.6 輪轉訪問MAC協議
- 輪轉訪問MAC協議簡介
- 8.3.7 MAC協議總結
- 9 局域網
- 9.1 ARP協議
- 9.1.1 ARP協議簡介
- 9.1.2 ARP: 地址解析協議
- 9.1.3 ARP協議在同一局域網內的工作機制（尋址）
- 9.1.4 ARP協議在不同局域網間的工作機制（尋址）
- 9.2 以太網
- 9.2.1 以太網
- 以太網：物理拓撲
- 以太網：不可靠、無連接服務
- 以太網CSMA/CD算法
- 以太網幀結構
- 802.3以太網標準: 鏈路與物理層
- 9.2.2 交換機
- 交換機: 多端口間同時傳輸
- 交換機轉發表：交換表
- 交換機: 自學習
- 交換機: 幀過濾/轉發
- 自學習與轉發過程舉例
- 交換機互聯
- 多交換機自學習舉例
- 組織機構(Institutional)網絡
- 9.2.3 交換機 vs. 路由器
- 9.2.4 網絡設備對比
- 9.2.5 虛擬局域網(VLAN)
- VLANs的研發動機
- VLANs
- 基于端口的VLAN
- 跨越多交換機的VLAN
- 802.1Q VLAN幀格式
- 9.3 PPP協議
- 9.3.1 點對點數據鏈路控制
- 9.3.2 PPP設計需求[RFC 1557]
- 9.3.3 PPP無需支持的功能
- 9.3.4 PPP數據幀
- 9.3.5 字節填充(Byte Stuffing)
- 9.3.6 PPP數據控制協議
- 9.4 802.11無線局域網
- 9.4.1 IEEE 802.11無線局域網
- 9.4.2 IEEE 802.11體系結構
- 9.4.3 802.11：信道與AP關聯
- 9.4.4 802.11AP關聯：被動掃描與主動掃描
- 9.4.5 802.11：多路訪問控制
- 9.4.6 IEEE 802.11 MAC協議: CSMA/CA
- 9.4.7 IEEE 802.11 MAC協議: CSMA/CA
- 9.4.8 沖突避免(CA): RTS-CTS交換
- 9.4.9 IEEE 802.11 MAC幀
5 網絡層（上)
5.1 網絡層服務
- 從發送主機向接收主機傳送數據段（segment）
- 發送主機：將數據段封裝到數據報（datagram）中
- 接收主機：向傳輸層交付數據段（segment）
- 每個主機和路由器都運行網絡層協議
- 路由器檢驗所有穿越它的IP數據報的頭部域
- 決策如何處理IP數據報
網絡層核心功能-轉發與路由
- 轉發(forwarding): 將分組從路由器的輸入端口轉移到合 適的輸出端口
- 路由(routing): 確定 分組從源到目的經過的路徑
- 路由算法 （routing algorithms）
- 路由算法 （routing algorithms）
網絡層核心功能-連接建立
- 某些網絡的重要功能:
- ATM, 幀中繼, X.25
- 數據分組傳輸之前兩端主機需要首先建立虛擬/邏輯連接
- 網絡設備（如路由器）參與連接的建立
- 網絡層連接與傳輸層連接的對比:
- 網絡層連接: 兩個主機之間 (路 徑上的路由器等網絡設備參與 其中)
- 傳輸層連接: 兩個應用進程之間（對中間網絡設備透明）
網絡層服務模型
-
Q: 網絡層為發送端（主機）到接收端（主機）的數據報傳送 “通道(channel)”提供什么樣的服務模型(service model)?
-
無連接服務(connection-less service):
- 不事先為系列分組的傳輸確定傳輸路徑
- 每個分組獨立確定傳輸路徑
- 不同分組可能傳輸路徑不同
- 數據報網絡(datagram network )
-
連接服務(connection service):
- 首先為系列分組的傳輸確定從源到目的經過的路徑 (建立連接)
- 然后沿該路徑（連接）傳輸系列分組
- 系列分組傳輸路徑相同
- 傳輸結束后拆除連接
- 虛電路網絡(virtual-circuit network )
5.2 虛電路網絡與數據報網絡
5.2.1 虛電路網絡
連接服務。結合了電路交換和分組交換的優點。
連接服務與無連接服務
- 數據報(datagram)網絡與虛電路(virtual-circuit)網 絡是典型兩類分組交換網絡
- 數據報網絡提供網絡層無連接服務
- 虛電路網絡提供網絡層連接服務
- 類似于傳輸層的無連接服務（UDP）和面向連接 服務（TCP），但是網絡層服務：
- 主機到主機服務
- 網絡核心實現
虛電路(Virtual circuits)
虛電路：一條從源主機到目的主機，類似于電路的路徑(邏輯連接)
- 分組交換
- 每個分組的傳輸利用鏈路的全部帶寬
- 源到目的路徑經過的網絡層設備共同完成虛電路功能
注意：盡管虛電路中采用了很多電路交換中的術語，但本質上是此非彼的關系。
- 通信過程：
- 呼叫建立(call setup)→數據傳輸 →拆除呼叫
- 每個分組攜帶虛電路標識(VC ID)，而不是目的主機地址
- 虛電路經過的每個網絡設備 （如路由器），維護每條經過它的虛電路連接狀態
- 鏈路、網絡設備資源(如帶寬 、緩存等)可以面向VC進行預分配
- 預分配資源=可預期服務性能
- 如ATM的電路仿真（CBR）
VC的具體實現
- 每條虛電路包括:
- 沿某條虛電路傳輸的分組，攜帶對應虛電路的 VCID，而不是目的地址
- 同一條VC ，在每段鏈路上的VCID通常不同
- 路由器轉發分組時依據VC轉發表改寫/替換虛電路號
VC轉發表
路由器R1的VC轉發表:
虛電路信令協議(signaling protocols)
- 用于VC的建立、維護與拆除
- 路徑選擇
- 應用于虛電路網絡
- 如ATM、幀中繼(frame-relay)網絡等
- 目前的Internet不采用
5.2.2 數據報網絡
- 網絡層無連接
- 每個分組攜帶目的地址
- 路由器根據分組的目的地址轉發分組
- 基于路由協議/算法構建轉發表
- 檢索轉發表
- 每個分組獨立選路
數據報轉發表
對應的，虛電路網絡有VC轉發表。
32位可存放40多億地址，但在分組有限的大小中這是很不現實的，所以分組是根據地址范圍來轉發的。
但這也出現了一個問題：
如果地址范圍劃分的不是這么“完美”會怎么樣？
解決辦法：最長前綴匹配優先。
最長前綴匹配優先
5.2.3 數據報網絡與VC網絡的對比
5.3 IPv4協議
5.3.1 IP協議（1）-IP數據報
IP數據報(分組)格式
- 版本號字段占4位：IP協議的版本號 ? E.g. 4→IPv4，6 → IPv6
- 首部長度字段占4位：IP分組首部長度
- 以4字節為單位
- E.g. 5→IP首部長度為20(5×4)字節
- 服務類型(TOS)字段占8位：指示期望獲得哪種類型的服務
- 1998 年這個字段改名為區分服務
- 只有在網絡提供區分服務(DiffServ)時使用
- 一般情況下不使用，通常IP分組的該字段(第2字節)的值為00H
- 總長度字段占16位：IP分組的總字節數(首部+數據)
- 最大IP分組的總長度：65535B
- 最小的IP分組首部：20B
- IP分組可以封裝的最大數據：65535-20=65515B
- 生存時間（TTL）字段占8位：IP分組在網絡中可以通過的 路由器數（或跳步數）
- 路由器轉發一次分組，TTL減1
- 如果TTL=0，路由器則丟棄該IP分組
- 協議字段占8位：指示IP分組封裝的是哪個協議的數據包
- 實現復用/分解
- E.g. 6為TCP，表示封裝的為TCP段；17為UDP，表示封裝的是UDP數據報
- 首部校驗和字段占16位：實現對IP分組首部的差錯檢測
- 計算校驗和時，該字段置全0
- 采用反碼算數運算求和，和的反碼作為首部校驗和字段
- 逐跳計算、逐跳校驗
- 源IP地址、目的IP地址字段各占32位：分別標識發送分組 的源主機/路由器(網絡接口)和接收分組的目的主機/路由器 （網絡接口）的IP地址
- 選項字段占長度可變，范圍在1~40B之間：攜帶安全、源選路徑、時間戳和路由記錄等內容
- 實際上很少被使用
- 填充字段占長度可變，范圍在0~3B之間：目的是補齊整個 首部，符合32位對齊，即保證首部長度是4字節的倍數
5.3.2 IP協議（2）-IP分片
最大傳輸單元(MTU)
- 網絡鏈路存在MTU (最大傳輸單元)——鏈路層數據幀可封裝數據的上限
- 不同鏈路的MTU不同
IP分片與重組
- 大IP分組向較小MTU鏈路轉發時，可以被“分片” (fragmented)
- 1個IP分組分為多片IP分組
- IP分片到達目的主機后進行“重組” (reassembled)
- IP首部的相關字段用于標識分片以及確定分片的相對順序
- 總長度、標識、標志位和片偏移
- 總長度、標識、標志位和片偏移
IP分組格式
- 標識字段占16位：標識一個IP分組
- IP協議利用一個計數器，每產生IP分組計數器加1，作為該IP分組 的標識
- 標志位字段占3位：
- DF (Don't Fragment)
- MF (More Fragment)
- DF =1：禁止分片；
DF =0：允許分片 - MF =1：非最后一片；
MF =0：最后一片(或未分片)
- 片偏移字段占13位：一個IP分組分片封裝原IP分組數據的相對偏移量
- 片偏移字段以8字節為單位
IP分片過程
- 假設原IP分組總長度為L，待轉發鏈路的MTU為M
- 若L>M，且DF=0，則可以/需要分片
- 分片時每個分片的標識復制原IP分組的標識
- 通常分片時，除最后一個分片，其他分片均分為MTU允 許的最大分片
- 一個最大分片可封裝的數據應該是8的倍數，因此，一個 最大分片可封裝的數據為:
d=?M?208?×8d=\biggl\lceil\frac{M-20}8\biggr\rceil\times8 d=?8M?20??×8 - 需要的總片數為：
n=?L?20d?n=\biggl\lceil\frac{L-20}d\biggr\rceil n=?dL?20?? - 每片的片偏移字段取值為：
Fi=d8×(i?1),1≤i≤nF_i=\frac d8\times(i-1),\quad 1\leq i\leq nFi?=8d?×(i?1),1≤i≤n - 每片的總長度字段為：
Li{d+201≤i≤nL?(n?1)di=nL_i \begin{cases} d+20 & \quad 1\leq i\leq n\\ L-(n-1)d &\quad i=n\\ \end{cases} Li?{d+20L?(n?1)d?1≤i≤ni=n? - 每片的MF標志位為：
MFi={11≤i<n0i=n{MF}_i=\begin{cases} 1 & \quad 1\leq i < n \\ 0 & \quad i=n \end{cases}MFi?={10?1≤i<ni=n?
5.3.3 IP協議（3）-IP編址
IP編址(addressing)
-
IP分組：
- 源地址(SA)-從哪兒來
- 目的地址(DA)-到哪兒去
-
接口(interface): 主機/路 由器與物理鏈路的連接
- 實現網絡層功能
- 路由器通常有多個接口
- 主機通常只有一個或兩個接口 (e.g.，有線的以太網接口，無線的802.11接口)
-
IP地址: 32比特(IPv4) 編號標識主機、路由器的接口
-
IP地址與每個接口關聯
-
怎樣為接口分配IP地址呢？
IP子網（Subnets）
- IP地址:
- 網絡號(NetID)– 高位比特
- 主機號(HostID)– 低位比特
- IP子網：
- IP地址具有相同網絡號的設備接口
- 不跨越路由器（第三及以 上層網絡設備）可以彼此物理聯通的接口
- 圖中網絡有多少個 IP子網?
六個。
5.3.4 IP協議（4）-有類IP地址
- IP地址:
- 網絡號(NetID)– 高位比特
- 主機號(HostID)– 低位比特
- IP子網：
- IP地址具有相同網絡號的設備接口
- 不跨越路由器（第三及以 上層網絡設備）可以彼此物理聯通的接口
有類IP地址
采用二分法。
-
特殊IP地址
-
私有（Private）IP地址
私有IP地址一般用于機構內部網絡，在公網中是無法與其通信的，私有IP地址增加了IP地址的復用性（因為公網連接不上，各個機構又是分開的）。
5.3.5 IP協議（4）-IP子網劃分與子網掩碼
-
IP地址:
- 網絡號(NetID)– 高位比特
- 主機號(HostID)– 低位比特
-
IP子網：
- IP地址具有相同網絡號的設備接口
- 不跨越路由器（第三及以 上層網絡設備）可以彼此物理聯通的接口
-
有類IP地址
如何進行子網劃分(Subnetting)？
- IP地址:
- 網絡號(NetID) – 高位比特
- 子網號(SubID) – 原網絡主機號部分比特
- 主機號(HostID) – 低位比特
-
如何確定是否劃分了子網？利用多少位劃分子網？
- 子網掩碼
-
子網掩碼
-
形如IP地址:
- 32位
- 點分十進制形式
-
取值：
- NetID、SubID位全取1
- HostID位全取0
-
例如：
- A網的默認子網掩碼為：255.0.0.0
- B網的默認子網掩碼為：255.255.0.0
- C網的默認子網掩碼為：255.255.255.0
- 借用3比特劃分子網的B網的子網掩碼為：255.255.224.0
-
子網劃分
-
例如：
- 子網201.2.3.0，255.255.255.0，劃分為等長的4個子網
- 子網201.2.3.0，255.255.255.0，劃分為等長的4個子網
-
路由器如何確定應該將IP分組轉發到哪個子網？
通過子網掩碼。
子網掩碼的應用
-
將IP分組的目的IP地址與子網掩碼按位與運算， 提取子網地址
-
例如：
- 目的IP地址：172.32.1.112，子網掩碼：255.255.254.0
- 子網地址：172.32.0.0(子網掩碼：255.255.254.0)
- 地址范圍：172.32.0.0~172.32.1.255
- 可分配地址范圍：172.32.0.1~172.32.1.254
- 廣播地址：172.32.1.255
- 目的IP地址：172.32.1.112，子網掩碼：255.255.254.0
-
一個C類網絡劃分子網舉例
6 網絡層（中)
6.1 CIDR與路由聚合
無類域間路由(CIDR: Classless InterDomain Routing)
- 消除傳統的 A 類、B 類和 C 類地址界限
- NetID+SubID→Network Prefix (Prefix)可以任意長度
- 融合子網地址與子網掩碼，方便子網劃分
- 無類地址格式：a.b.c.d/x，其中x為前綴長度
- 例如
- 子網201.2.3.64，255.255.255.192→201.2.3.64/26
CIDR與路由聚合的作用
- 提高IPv4 地址空間分配效率
- 提高路由效率
- 將多個子網聚合為一個較大的子網
- 構造超網（supernetting）
- 路由聚合（route aggregation）
路由聚合
- 將多個子網聚合，大大縮小了路由中的轉發表的大小
- 層級編址使得路由信息通告更高效:
但是層級編制會出現一個問題：聚合之后的地址可能會包括其它子網中的地址，如下圖中的200.23.18.2/23，這是就要遵循最長前綴匹配優先原則了。
劃分子網的意義是什么？如何進行子網劃分？什么是定長子網劃分？什么是變長子網劃分？如何準確地描述一個子網？為什么要進行路由聚集？如何進行路由聚集？什么情況下可以進行路由聚集？
6.2 DHCP協議
-
如何獲得IP地址?
Q: 一個主機如何獲得IP地址？- “硬編碼”
- 靜態配置
- 動態主機配置協議-DHCP: Dynamic Host Configuration Protocol
- 從服務器動態獲取：
- IP地址
- 子網掩碼
- 默認網關地址
- DNS服務器名稱與IP地址
- “即插即用”
- 允許地址重用
- 支持在用地址續租
DHCP協議給客戶端分配的地址是有時間限制的。 - 支持移動用戶加入網絡
- 從服務器動態獲取：
- 動態主機配置協議(DHCP)
- 主機廣播 “DHCP discover”(發現報文)
- DHCP服務器利用 “DHCP offer” (提供報文) 進行響應
- 主機請求IP地址: “DHCP request” (請求報文)
- DHCP服務器分配IP地址: “DHCP ack” (確認報文)
- DHCP工作過程示例
- DHCP協議實現于應用層
- 請求報文封裝到UDP數據報中
- IP廣播
- 鏈路層廣播
(e.g. 以太網廣播)
- DHCP服務器構造 ACK報文
- 包括分配給客戶的 IP地址、子網掩碼 、默認網關、DNS 服務器地址
- 包括分配給客戶的 IP地址、子網掩碼 、默認網關、DNS 服務器地址
- DHCP協議實現于應用層
- “硬編碼”
6.3 網絡地址轉換(NAT)
- 研究NAT的動機
- 只需/能從ISP申請一個IP地址
- IPv4地址耗盡
- 本地網絡設備IP地址的變更，無需通告外界 網絡
- 變更ISP時，無需修改內部網絡設備IP地址
- 內部網絡設備對外界網絡不可見，即不可直接尋址(安全)
- 只需/能從ISP申請一個IP地址
- 優點及爭議
- 16-bit端口號字段:
- 可以同時支持60,000多并行連接！
- NAT主要爭議:
- 路由器應該只處理第3層功能
- 違背端到端通信原則
- 應用開發者必須考慮到NAT的存在，e.g., P2P應用
- 地址短缺問題應該由IPv6來解決
- 16-bit端口號字段:
6.3.1 NAT的實現
-
實現:
- 替換
- 利用(NAT IP地址,新端口號)替換每個外出IP數據報的(源IP地址,源端口號)
- 記錄
- 將每對(NAT IP地址, 新端口號) 與(源IP地址, 源端 口號)的替換信息存儲到NAT轉換表中
- 替換
- 根據NAT轉換表，利用(源IP地址, 源端口號)替換每個進入內網IP數據報的(目的IP地址,目的端口號)， 即(NAT IP地址, 新端口號)
- 替換
-
NAT的執行過程舉例：
6.3.2 NAT穿透問題
- 客戶期望連接內網地址為 10.0.0.1的服務器
- 客戶不能直接利用地址 10.0.0.1直接訪問服務器
- 對外唯一可見的地址是NAT 地址: 138.76.29.7
- 解決方案:
-
1:
靜態配置NAT ，將特定端口的連接請求轉發給服務器- e.g., (138.76.29.7, 2500) 總是轉發給(10.0.0.1, 25000)
- e.g., (138.76.29.7, 2500) 總是轉發給(10.0.0.1, 25000)
-
2:
利用UPnP (Universal Plug and Play) 互聯網網關設備協議 (IGDInternet Gateway Device ) 自動配置:- 學習到NAT公共IP地址 (138.76.29.7)
- 在NAT轉換表中，增刪端口映射
-
3:
中繼(如Skype)- NAT內部的客戶與中繼服務器建立連接
- 外部客戶也與中繼服務器建立連接
- 中繼服務器橋接兩個連接的分組
-
6.4 互聯網控制報文協議(ICMP)
- 互聯網控制報文協議 ICMP (Internet Control Message Protocol)支持主機或路由器：
- 差錯(或異常)報告
- 網絡探詢
- 兩類 ICMP 報文:
- 差錯報告報文(5種)
- 目的不可達
- 源抑制(Source Quench)
- 超時/超期
- 參數問題
- 重定向 (Redirect)
- 網絡探詢報文(2組)
- 回聲(Echo)請求與應答報文(Reply)
- 時間戳請求與應答報文
- 差錯報告報文(5種)
- ICMP報文
- 例外情況 :
- 幾種不發送 ICMP差錯報告報文的特殊情況：
- 對ICMP差錯報告報文不再發送 ICMP差錯報告報文
- 除第1個IP數據報分片外，對所有后續分片均不發送ICMP差錯 報告報文
- 對所有多播IP數據報均不發送 ICMP差錯報告報文
- 對具有特殊地址（如127.0.0.0 或 0.0.0.0）的IP數據報不發送 ICMP 差錯報告報文
- 幾種 ICMP 報文已不再使用
- 信息請求與應答報文
- 子網掩碼請求和應答報文
- 路由器詢問和通告報文
- 幾種不發送 ICMP差錯報告報文的特殊情況：
- 例外情況 :
6.4.1 ICMP報文的格式
ICMP報文封裝到IP數據報中傳輸。
6.4.2 ICMP差錯報告報文數據封裝
6.4.3 ICMP的應用舉例：Traceroute
-
源主機向目的主機發送一系列 UDP 數據報
- 第1組IP數據報TTL =1
- 第2組IP數據報TTL=2, etc.
TTL是 Time To Live的縮寫，該字段指定IP包被路由器丟棄之前允許通過的最大網段數量。TTL是IPv4包頭的一個8 bit字段。
- 目的端口號為不可能使用的端口號
-
當第n組數據報(TTL=n)到達第 n 個路由器時：
- 路由器丟棄數據報
- 向源主機發送ICMP報文 (type=11, code=0)
- ICMP報文攜帶路由器名稱和 IP地址信息
-
當ICMP報文返回到源主機時， 記錄RTT
-
停止準則:
- UDP數據報最終到達目的主機
- 目的主機返回“目的端口不可達”ICMP報文 (type=3, code=3)
- 源主機停止
6.5 IPv6簡介
6.5.1 IPv6的研發動機
- 最初動機: 32位IPv4地址空間已分配殆盡
- 其他動機: 改進首部格式
- 快速處理/轉發數據報
- 支持QoS
- IPv6數據報格式:
- 固定長度的40字節基本首部
- 不允許分片
6.5.2 IPv6數據報格式
優先級(priority): 標識數據報的優先級
流標簽(flow Label): 標識同一“流”中的數據報
下一個首部(next header): 標識下一個選項首部或上層協議首部(如TCP首部)
6.5.3 其他改變 vs IPv4
- 校驗和(checksum): 徹底移除，以減少每跳處理 時間
- 選項(options): 允許，但是從基本首部移出，定義 多個選項首部，通過“下一個首部”字段指示
- ICMPv6: 新版ICMP
- 附加報文類型，e.g. “Packet Too Big”
- 多播組管理功能
6.5.4 IPv6地址表示形式
-
一般形式:
1080:0:FF:0:8:800:200C:417A -
壓縮形式:
FF01:0:0:0:0:0:0:43 壓縮→ FF01::43 -
IPv4-嵌入形式:
0:0:0:0:0:FFFF:13.1.68.3
或 ::FFFF:13.1.68.3 -
地址前綴:
2002:43c:476b::/48 (注: IPv6不再使用掩碼!) -
URLs:
http://[3FFE::1:800:200C:417A]:8000
6.5.5 IPv6基本地址類型
6.5.6 IPv4向IPv6過渡
- 不可能在某個時刻所有路由器同時被更新為IPv6
- 不會有 “標志性的日期”
- IPv4和IPv6路由器共存的網絡如何運行？
- 隧道(tunneling): IPv6數據報作為IPv4數據報的載 荷進行封裝，穿越IPv4網絡
- 隧道技術：
- 隧道技術：
6.6 典例講解
題目：
- 題目描述
- 題目：
解答：
- (1)
- (2)
- (3)
7 網絡層（下）
7.1~7.5：路由算法部分
7.6~7.9：Internet路由部分
7.1 路由算法概述
- 網絡抽象：圖
圖: G = (N, E)
N = 路由器集合= { u, v, w, x, y, z }
E = 鏈路集合 ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
附注: 圖的抽象在網絡領域應用很廣泛 E.g.:P2P，其中，N是 peers集合，而E是TCP連接集合
網
- 圖抽象：費用(Costs)
c(x, x’) = 鏈路(x, x’)的費用 e.g., c(w, z) = 5
每段鏈路的費用可以總是1，
或者是，
帶寬的倒數(帶寬越大，其倒數越小)、擁塞程度等 。
路徑費用：(x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
- 路由算法分類
- 靜態路由 vs 動態路由？
- 靜態路由：
- 手工配置
- 路由更新慢
- 優先級高
- 動態路由：
- 路由更新快
- 定期更新
- 及時響應鏈路費用或 網絡拓撲變化
- 路由更新快
- 靜態路由：
- 全局信息 vs 分散信息？
- 全局信息：
- 所有路由器掌握完整的網絡 拓撲和鏈路費用信息
- E.g. 鏈路狀態(LS)路由算法
- 分散(decentralized)信息：
- 路由器只掌握物理相連的鄰 居以及鏈路費用
- 鄰居間信息交換、運算的迭 代過程
- E.g. 距離向量(DV)路由算法
- 全局信息：
- 靜態路由 vs 動態路由？
7.2 鏈路狀態路由算法
- 網絡抽象：圖
圖: G = (N, E)
N = 路由器集合= { u, v, w, x, y, z }
E = 鏈路集合 ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
7.2.1 Dijkstra 算法
Dijkstra 算法
- 所有結點(路由器)掌握網 絡拓撲和鏈路費用
- 通過“鏈路狀態廣播”
- 所有結點擁有相同信息
- 計算從一個結點(“源”) 到達所有其他結點的最短路徑
- 獲得該結點的轉發表
- 迭代: k次迭代后，得到 到達k個目的結點的最短 路徑
符號:
- c(x,y): 結點x到結點y鏈路 費用；如果x和y不直接相 連，則=∞
- D(v): 從源到目的v的當前 路徑費用值
- p(v): 沿從源到v的當前路徑，v的前序結點
- N’: 已經找到最小費用路徑的結點集合
偽代碼：
Dijkstra算法舉例說明：
- 1
- 2
- u的最終最短路徑樹:
- u的最終轉發表:
- u的最終最短路徑樹:
Dijkstra 算法:討論
- 算法復雜性: n個結點
- 每次迭代: 需要檢測所有不在集合N’中的結點w
- n(n+1)/2次比較: O(n2)
- 更高效的實現: O(nlogn)
- 存在震蕩(oscillations)可能:
- e.g., 假設鏈路費用是該鏈路承載的通信量:
震蕩發生后，可能會出現這樣的情況：
分組從B->C->D之后，又從D->C，這樣子永遠都無法B->C->D->A。
- e.g., 假設鏈路費用是該鏈路承載的通信量:
7.3 距離向量路由算法(1)
距離向量(Distance Vector)路由算法。
- Bellman-Ford 舉例
- 距離向量路由算法
7.4 距離向量路由算法（2）
-
距離向量路由算法：舉例
-
距離向量DV: 鏈路費用變化
鏈路費用變化:
- 結點檢測本地鏈路費用變化
- 更新路由信息，重新計算距離向量
- 如果DV改變，通告所有鄰居
7.4.1 距離向量DV: 無窮計數問題
在上圖可以看到，如果xy之間的距離變成60，是不會直接改為60的，而是從一個初始值（上圖中的初始值是6）逐漸增大至60.- 解決無窮計數問題的方法：
-
1 毒性逆轉(poisoned reverse):
這個毒性逆轉問題感覺PPT中展示的不是很清楚，我先把PPT放上來，后續補上其他材料
如果一個結點(e.g. Z)到達某目的(e.g.X)的最小 費用路徑是通過某個鄰居(e.g.Y)，則：- 通告給該鄰居結點到達該目的的距離為無窮大
如果網絡結構很復雜，毒性逆轉技術也無法解決無窮計數問題。
- 通告給該鄰居結點到達該目的的距離為無窮大
-
2 定義最大度量(maximum metric):
- 定義一個最大的有效費用值，如15跳步，16跳步表示∞
(上圖的意思是：R1現如今無法直達192.168.1.1/24，但之前是可以的，當時R2到192.168.1.0/24的路徑R2->R1->192.168.1.0/24路徑是已被保留下來的（2跳），所以現如今R1到192.168.1.0/24的路徑（實際上是不可能存在的路徑）就會被當成R1->R2->R1->192.168.1.0/24（3跳）)
然后一直增加到15或16跳步時就被當作∞了，這樣就不會繼續計數下去，也就說避免了無窮計數問題。
- 定義一個最大的有效費用值，如15跳步，16跳步表示∞
-
7.5 層次路由
- 將任意規模網絡抽象為一個圖計算路由-過于理想化
- 標識所有路由器
- “扁平”網絡 ——在實際網絡（尤其是大規模網絡）中，不可行！
7.5.1 研發層次路由的動機
- 網絡規模：考慮6億目 的結點的網絡
- 路由表幾乎無法存儲！
- 路由計算過程的信息 （e.g. 鏈路狀態分組、 DV）交換量巨大，會淹沒鏈路！
- 管理自治：
- 每個網絡的管理可能都期望自主控制其網內的路由
- 互聯網(internet) = 網絡之 網絡(network of networks)
7.5.2 層次路由詳述
- 聚合路由器為一個區域 ：自治系統AS (autonomous systems)
- 同一AS內的路由器運行相同的路由協議(算法)
- 自治系統內部路由協議 (“intra-AS” routing protocol)
- 不同自治系統內的路由 器可以運行不同的AS內部路由協議
- 網關路由器(gateway router):
- 位于AS“邊緣”
- 通過鏈路連接其他AS的網關路由器
互連的AS
- 轉發表由AS內部路由算法與AS間路由算法共同配置
- AS內部路由算法設置AS內部目的網絡路由入口(entries)
- AS內部路由算法與AS間路由算法共同設置 AS外部目的網絡路由入口
互
自治系統間(Inter-AS)路由任務
- 假設AS1內某路由器收到一個目的地址在AS1 之外的數據報:
- 路由器應該將該數據報轉發給哪個網關路由器呢？
AS1必須:
舉例說明層次路由
-
例2: 路由器1d的轉發表設置
- 假設AS1學習到(通過AS間路由協議)：子網x可以通過AS3 (網關 1c)到達，但不能通過AS2到達
- AS間路由協議向所有內部路由器傳播該可達性信息
- 路由器1d：利用AS內部路由信息，確定其到達1c 的最小費用路徑接口/
- 在1d轉發表中增加入口：(x, /)
- 在1d轉發表中增加入口：(x, /)
- 假設AS1學習到(通過AS間路由協議)：子網x可以通過AS3 (網關 1c)到達，但不能通過AS2到達
-
例2: 在多AS間選擇
- 假設AS1通過AS間路由協議學習到：子網x通過 AS3和AS2均可到達
- 為了配置轉發表，路由器1d必須確定應該將去往子網x的數據報轉發給哪個網關？
- 這個任務也是由AS間路由協議完成!
- 這個任務也是由AS間路由協議完成!
-
例3: 在多AS間選擇
- 假設AS1通過AS間路由協議學習到：子網x通過 AS3和AS2均可到達
- 為了配置轉發表，路由器1d必須確定應該將去往子網x的數據報轉發給哪個網關？
- 這個任務也是由AS間路由協議完成!
- 熱土豆路由: 將分組發送給最近的網關路由器.
7.6 RIP協議
7.6.1 AS內部路由
- Internet采用層次路由
- AS內部路由協議也稱為內部網絡協議IGP (interior gateway protocols)
- 最常見的AS內部路由協議:
- 路由信息協議：RIP(Routing Information Protocol)
- 開放最短路徑優先：OSPF(Open Shortest Path First)
- 內部網關路由協議：IGRP(Interior Gateway Routing Protocol)
- Cisco私有協議
7.6.2 RIP
-
早于1982年隨BSD-UNIX操作系統發布
-
距離向量路由算法
- 距離度量：跳步數 (max = 15 hops), 每條鏈路1個跳步
- 每隔30秒，鄰居之間交換一次DV，成為通告(advertisement)
- 每次通告：最多25個目的子網(IP地址形式)
-
舉例：
默認D到A的跳步為1，現D到z所需跳步為7，但A到z跳步為4，所以將D->z變成D->A->后所需跳步為5。所以說RIP的實質就是距離最短算法。 -
RIP: 鏈路失效、恢復
如果180秒沒有收到通告→鄰居/鏈路失效- 經過該鄰居的路由不可用
- 重新計算路由
- 向鄰居發送新的通告
- 鄰居再依次向外發送通告（如果轉發表改變）
- 鏈路失效信息能否快速傳播到全網？
- 可能發生無窮計數問題
- 毒性逆轉技術用于預防乒乓(ping-pong)環路 (另外：無窮大距離 = 16 hops)
- 經過該鄰居的路由不可用
-
RIP路由表的處理
- RIP路由表是利用一個稱作route-d (daemon)的應用層進程進行管理
- 應用進程實現
- 通告報文周期性地通過UDP數據報發送
- RIP路由表是利用一個稱作route-d (daemon)的應用層進程進行管理
7.7 OSPF協議簡介
OSPF (Open Shortest Path First)
- “開放”: 公眾可用
- 采用鏈路狀態路由算法
- LS分組擴散（通告）
- 每個路由器構造完整的網絡(AS)拓撲圖
- 利用Dijkstra算法計算路由
- OSPF通告中每個入口對應一個鄰居
- OSPF通告在整個AS范圍泛洪
- OSPF報文直接封裝到IP數據報中
- 與OSPF極其相似的一個路由協議:IS-IS 路由協議
7.7.1 OSPF優點(RIP不具備)
- 安全(security): 所有OSPF報文可以被認證 (預防惡意入侵)
- 允許使用多條相同費用的路徑 (RIP只能選一條)
- 對于每條鏈路，可以針對不同的服務類型TOS設置多個不同的費用度量 (e.g., 衛星鏈路可以針對“盡力” (best effort) ToS設置“低”費用；針對實時ToS 設置“高”費用)
- 集成單播路由與多播路由:
- 多播OSPF協議(MOSPF) 與OSPF利用相同的 網絡拓撲數據
- OSPF支持對大規模AS分層(hierarchical)
在7.7.2詳細敘述。
7.7.2 分層的OSPF
注意區分區邊界路由器和AS邊界路由器的不同。
7.8 BGP協議簡介
Internet AS間路由協議: BGP 。
- 邊界網關協議BGP (Border Gateway Protocol): 事實上的標準域間路由協議
- 將Internet “粘合”為一個整體的關鍵
- BGP為每個AS提供了一種手段:
- eBGP: 從鄰居AS獲取子網可達性信息.
- iBGP: 向所有AS內部路由器傳播子網可達性信息.
- 基于可達性信息與策略，確定到達其他網絡的 “好” 路徑.
- 容許子網向Internet其余部分通告它的存在： “我在這兒！”
7.8.1 BGP基礎
- BGP會話(session): 兩個BGP路由器 (“Peers”) 交換BGP報文:
- 通告去往不同目的前綴（prefix）的路徑 (“路徑向量 (path vector)”協議)
這里所謂的"前綴"是指子網。
而且這里是路徑向量而不是RIP協議的距離向量，二者是不同的。 - 報文交換基于半永久的TCP連接
- 通告去往不同目的前綴（prefix）的路徑 (“路徑向量 (path vector)”協議)
- BGP報文:
- OPEN: 與peer建立TCP連接，并認證發送方
- UPDATE: 通告新路徑 (或撤銷原路徑)
- KEEPALIVE: 在無UPDATE時，保活連接；也用于對 OPEN請求的確認
- NOTIFICATION: 報告先前報文的差錯；也被用于關閉 連接
- 當AS3通告一個前綴給AS1時:
- AS3承諾可以將數據報轉發給該子網
- AS3在通告中會聚合網絡前綴
7.8.2 BGP基礎: 分發路徑信息
- 在3a與1c之間, AS3利用eBGP會話向AS1發送前綴可達性信息.
- 1c則可以利用iBGP向AS1內的所有路由器分發新的前綴可達 性信息
- 1b可以（也可能不）進一步通過1b-到-2a的eBGP會話，向 AS2通告新的可達性信息
- 當路由器獲得新的前綴可達性時，即在其轉發表中增加關于該前綴的入口（路由項）
7.8.3 路徑屬性與BGP路由（route）
- 通告的前綴信息包括BGP屬性
- 前綴+屬性= “路由”
- 兩個重要屬性:
- AS-PATH(AS路徑): 包含前綴通告所經過的AS序列: e.g., AS 67, AS 17
- NEXT-HOP(下一跳): 開始一個AS-PATH的路由器接口，指向下一 跳AS.
- 可能從當前AS到下一跳AS存在多條鏈路
如AS2中，此時熱土豆路由就派上用場了。
- 可能從當前AS到下一跳AS存在多條鏈路
7.8.4 BGP路由選擇
- 網關路由器收到路由通告后，利用其輸入策略 (import policy)決策接受/拒絕該路由
- e.g., 從不將流量路由到AS x
- 基于策略(policy-based) 路由
- 路由器可能獲知到達某目的AS的多條路由，基于 以下準則選擇：
7.8.5 BGP路由選擇策略舉例
-
上圖的各組成元素的所代表的意思：
- A,B,C是提供商網絡/AS(provider network/AS)
- X,W,Y是客戶網絡(customer network/AS)
- W,Y是樁網絡(stub network/AS): 只與一個其他AS相連
- X是雙宿網絡(dual-homed network/AS): 連接兩個其他AS
- X不期望經過他路由B到C的流量
- … 因此，X不會向B通告任何一條到達C的路由
-
上圖路由策略：
- A向B通告一條路徑：AW
- B向X通告路徑：BAW
- B是否應該向C通告路徑BAW呢?
- 絕不! B路由CBAW的流量沒有任何“收益”， 因為W和C均不是B的客戶。
- B期望強制C通過A向W路由流量
- B期望只路由去往/來自其客戶的流量！
7.8.6 為什么采用不同的AS內與AS間路由協議?
說明：
inter-AS: 自治系統間
inter-AS: 自治系統內
-
策略(policy):
- inter-AS: 期望能夠管理控制流量如何被路由，誰路由 經過其網絡等.
- intra-AS: 單一管理，無需策略決策
-
規模(scale):
- 層次路由節省路由表大小，減少路由更新流量
- 適應大規模互聯網
-
性能(performance):
- intra-AS: 側重性能
- inter-AS: 策略主導
8 數據鏈路層
8.1 數據鏈路層服務
8.1.1 概述
術語:
- 主機和路由器：結點(nodes)
在數據鏈路層主機和路由器均被視作結點。 - 連接相鄰結點的通信信道：鏈路 (links)
- 有線鏈路(wired links)
- 無線鏈路(wireless links)
- 局域網(LANs)
- 鏈路層(第2層)數據分組：幀 (frame)，封裝網絡層數據報
8.1.2 鏈路層服務
- 組幀(framing)
- 封裝數據報構成數據幀，加首部和尾部
- 幀同步
- 鏈路接入(link access)
- 如果是共享介質，需要解決信道接入(channel access)
- 幀首部中的“MAC”地址，用于標識幀的源和目的
- 不同于IP地址！
- 相鄰結點間可靠交付
- 在低誤碼率的有線鏈路上很少采用 (如光纖，某些雙絞線等)
- 無線鏈路：誤碼率高，需要可靠交付
- 流量控制(flow control)
- 協調(pacing)相鄰的發送結點和接收結點
- 差錯檢測(error detection)
- 信號衰減和噪聲會引起差錯.
- 接收端檢測到差錯:
- 通知發送端重傳或者直接丟棄幀
- 差錯糾正(error correction)
- 接收端直接糾正比特差錯
- 全雙工和半雙工通信控制
- 全雙工：鏈路兩端結點同時雙向傳輸
- 半雙工：鏈路兩端結點交替雙向傳輸
8.1.3 鏈路層的具體實現？
- 由每個主機或路由器接口實現
- 鏈路層在“適配器” (即網絡接口卡-NIC)中實現或者在一個芯片上實現
- 以太網網卡，802.11網卡 ；以太網芯片組
- 實現鏈路層和物理層
- 鏈接主機的系統總線
- 由硬件、軟件與固件組成
8.1.4 網卡間通信
- 發送端：
- 將數據報封裝成幀
- 增加差錯檢測比特，實現可靠數據傳輸和流量控制等.
- 接收端：
- 檢測差錯，實現可靠數據傳輸和流量控制等
- 提取數據報，交付上層協議實體
8.2 差錯編碼
用于差錯檢測和差錯糾正。
差錯編碼是通過想方設法增加其漢明距離來達到差錯檢測和差錯糾正的。
注意：此圖只表示了差錯檢測，未表示差錯糾正。
8.2.1 差錯編碼的檢錯能力
- 差錯編碼可分為檢錯碼與糾錯碼
- 對于檢錯碼，如果編碼集的漢明距離ds=r+1ds=r+1ds=r+1，則該差錯編碼可以檢測rrr位的差錯
- 例如，編碼集 {0000,0101,1010,1111} 的漢明距離ds=2，可以 100%檢測1比特差錯
- 對于糾錯碼，如果編碼集的漢明距離ds=2r+1ds=2r+1ds=2r+1，則該差錯編碼可以糾正rrr位的差錯
- 例如，編碼集 {000000,010101,101010,111111} 的漢明距離ds=3 ，可以糾正1比特差錯，如100010糾正為101010。
8.2.2 奇偶校驗碼
無論是奇校驗還是偶校驗，都只能檢測奇位數錯誤而無法檢測偶位數錯誤。
補充材料：
奇偶校驗碼淺談 https://www.cnblogs.com/dushikang/p/8334776.html
8.2.3 Internet校驗和(Checksum)
- 發送端:
- 將“數據”(校驗內容) 劃分為16位的二進制 “整數”序列
- 求和(sum)：補碼求和 (最高位進位的“1”， 返回最低位繼續加）
- 校驗和(Checksum)： sum的反碼
- 放入分組(UDP、TCP 、IP)的校驗和字段
- 接收端:
- 與發送端相同算法計算
- 計算得到的"checksum"：
- 為16位全0（或sum為16位 全1）：無錯
- 否則：有錯
8.2.4 循環冗余校驗碼(CRC)
檢錯能力更強大的差錯編碼。
-
CRC的原理：
- 將數據比特，D，視為一個二進制數
- 選擇一個r+1位的比特模式 (生成比特模式)，G
- 目標：選擇r位的CRC比特，R，滿足
- <D,R>剛好可以被G整除(模2)
- 接收端檢錯：利用G除<D,R>，余式全0，無錯；否則，有錯！
- 可以檢測所有突發長度小于r+1位差錯。
-
廣泛應用于實際網絡 (以太網，802.11 WiFi，ATM)
-
CRC舉例：
補充材料：
CRC校驗碼的計算示例
由以上分析可知，既然除數是隨機，或者按標準選定的，所以CRC校驗的關鍵是如何求出余數，也就是CRC校驗碼。
下面以一個例子來具體說明整個過程。現假設選擇的CRC生成多項式為 G(X)=X4+X3+1G(X)=X4+X3+1G(X)=X4+X3+1 ，要求出二進制序列10110011的CRC校驗碼。下面是具體的計算過程：
8.3 多路訪問控制(MAC)協議
MAC協議決定了節點什么時候允許發送分組，而且通常控制對物理層的所有訪問。
-
兩類“鏈路”：
- 點對點鏈路
- 撥號接入的PPP
- 以太網交換機與主機間的點對點鏈路
- 廣播鏈路 (共享介質)
- 早期的總線以太網
- HFC的上行鏈路
- 802.11無線局域網
- 點對點鏈路
-
單一共享廣播信道
-
兩個或者兩個以上結點同時傳輸：干擾(interference)
- 沖突(collision)
- 結點同時接收到兩個或者多個信號→接收失敗！
- 沖突(collision)
-
多路訪問控制協議(multiple access control protocol)
- 采用分布式算法決定結點如何共享信道，即決策結點何時可以傳輸數據
- 必須基于信道本身，通信信道共享協調信息！
- 無帶外信道用于協調
8.3.1 理想MAC協議
給定：速率為R bps的廣播信道
期望：
- 無需特定結點協調
- 無需時鐘、時隙同步
8.3.2 MAC協議分類
三大類：
- 信道劃分(channel partitioning)MAC協議
- 多路復用技術
- TDMA、FDMA、CDMA、WDMA等
- 隨機訪問(random access)MAC協議
- 信道不劃分，允許沖突
- 采用沖突“恢復”機制
- 輪轉(“taking turns”)MAC協議
- 結點輪流使用信道
8.3.3 信道劃分MAC協議
TDMA
TDMA: time division multiple access
- “周期性”接入信道
- 每個站點在每個周期，占用固定長度的時隙(e.g.長度= 分組傳輸時間)
- 未用時隙空閑(idle)
- 例如：6-站點LAN，1,3,4傳輸分組，2,5,6空閑
如上圖所示，2、5、6是未被使用的，這造成了資源的浪費。
FDMA
FDMA: frequency division multiple access
- 信道頻譜劃分為若干頻帶(frequency bands)
- 每個站點分配一個固定的頻帶
- 無傳輸頻帶空閑
- 例如: 6站點LAN, 1,3,4頻帶傳輸數據, 2,5,6頻帶空閑。
有些頻段是沒被使用的，這造成了資源的浪費。
8.3.5 隨機訪問MAC協議
- 當結點要發送分組時：
- 利用信道全部數據速率R發送分組
- 沒有事先的結點間協調
- 兩個或多個結點同時傳輸：? “沖突”
- 隨機訪問MAC協議需要定義:
- 如何檢測沖突
- 如何從沖突中恢復 (e.g., 通過延遲重傳)
- 典型的隨機訪問MAC協議：
- 時隙(sloted)ALOHA
- ALOHA，也稱純ALOHA
- CSMA、CSMA/CD、CSMA/CA
時隙ALOHA協議 (S-ALOHA)
- 假定：
- 所有幀大小相同
- 時間被劃分為等長的時隙 (每個時隙可以傳輸1個幀)
- 結點只能在時隙開始時刻發送幀
- 結點間時鐘同步
- 如果2個或2個以上結點在 同一時隙發送幀，結點即檢測到沖突
- 運行:
- 當結點有新的幀時，在下 一個時隙(slot)發送
- 如果無沖突：該結點可以在下一個時隙繼續發 送新的幀
- 如果沖突：該結點在下 一個時隙以概率p重傳該幀，直至成功
- 當結點有新的幀時，在下 一個時隙(slot)發送
-
優點:
- 單個結點活動時，可以 連續以信道全部速率傳 輸數據
- 高度分散化：只需同步時隙
- 簡單
-
缺點:
- 沖突，浪費時隙
- 空閑時隙
- 結點也許能以遠小于分組傳輸時間檢測到沖突
- 時鐘同步
-
效率分析：
- 假設: NNN個結點有很多幀待傳輸，每個結點在每個時隙均以概率p發送數據
- 對于給定的一個結點，在 一個時隙將幀發送成功的 概率= p(1?p)N?1p(1-p)^{N-1}p(1?p)N?1
- 對于任意結點成功發送幀的概率= Np(1?p)N?1Np(1-p)^{N-1}Np(1?p)N?1
- 最大效率: 求得使Np(1?p)N?1Np(1-p)^{N-1}Np(1?p)N?1最大的p*
- 對于很多結點，求 Np?(1?p?)N?1Np*(1-p*)^{N-1}Np?(1?p?)N?1當N趨近無 窮時的極限，可得:
最大效率= 1/e = 0.37
ALOHA協議
- 非時隙(純)Aloha：更加簡單，無需同步
- 當有新的幀生成時
- 立即發送
- 沖突可能性增大:
- 在t0時刻發送幀，會與在[t0?1,t0+1][t_0-1, t_0+1][t0??1,t0?+1]（易損時間區）期間其他結點發送的幀沖突
- 在t0時刻發送幀，會與在[t0?1,t0+1][t_0-1, t_0+1][t0??1,t0?+1]（易損時間區）期間其他結點發送的幀沖突
- 效率分析：
CSMA協議
- 載波監聽多路訪問協議 CSMA (carrier sense multiple access)
- 發送幀之前，監聽信道 (載波)：
- 信道空閑：發送完整幀
- 信道忙：推遲發送
- 1-堅持CSMA
- 非堅持CSMA
- P-堅持CSMA
- 沖突可能仍然發生： 信號傳播延遲
- 繼續發送沖突幀：浪費信道資源
上圖是B和D同時監聽到信道中無沖突，課這樣B和D又產生了沖突從而造成信道浪費。
CSMA/CD協議
特點：發送分組的時候保持監聽，不發送的時候斷開監聽。
- CSMA/CD: CSMA with Collision Detection
- 短時間內可以檢測到沖突
- 沖突后傳輸中止，減少信道浪費
- 沖突檢測:
- 有線局域網易于實現：測量信號強度，比較發射信號與接收信號
- 無線局域網很難實現：接收信號強度淹沒在本地發射信號強度下
- 實現CSMA/CD的前提
例題：
- CSMA/CD的效率
- TpropT_{prop}Tprop? = LAN中2個結點間的最大傳播延遲
- ttranst_{trans}ttrans? = 最長幀傳輸延遲
效率=11+5tprop/ttrans\textbf效\textbf率\textbf =\frac 1{1+5t_{prop}/t_{trans}}效率=1+5tprop?/ttrans?1?
- tpropt_{prop}tprop? 趨近于0或者ttranst_{trans}ttrans?趨近于∞∞∞時，效率趨近于1
- 遠優于ALOHA，并且簡單、分散！
8.3.6 輪轉訪問MAC協議
- 信道劃分MAC協議：
- 網絡負載重時，共享信道效率高，且公平
- 網絡負載輕時，共享信道效率低！
- 隨機訪問MAC協議：
- 網絡負載輕時，共享信道效率高，單個結點可以利用 信道的全部帶寬
- 網絡負載重時，產生沖突開銷
- 輪轉訪問MAC協議： 綜合兩者的優點！
輪轉訪問MAC協議簡介
- 輪詢(polling):
- 主結點輪流“邀請” 從屬結點發送數據
- 典型應用： “啞(dumb)” 從屬 設備
輪
- 問題：
- 輪詢開銷
- 等待延遲
如下圖，每個slave需要等到master叫到（輪著叫的）才能發送數據。
- 單點故障
- 令牌傳遞(token passing):
- 控制令牌依次從一個結 點傳遞到下一個結點.
- 令牌：特殊幀
- 控制令牌依次從一個結點傳遞到下一個結點.
- 令牌：特殊幀
- 問題:
- 令牌開銷
- 等待延遲
假設令牌剛從這臺機器發出，又得輪一圈才能回來。
- 單點故障
8.3.7 MAC協議總結
- 信道劃分MAC協議：時間、頻帶、碼片劃分
- TDMA、FDMA、CDMA
- 隨機訪問MAC協議：
- ALOHA, S-ALOHA, CSMA, CSMA/CD
- CSMA/CD應用于以太網
- CSMA/CA應用802.11無線局域網
- 輪轉訪問MAC協議：
- 綜合了上面兩個MAC協議的優點，算是折中的一種存在。
- 主結點輪詢；令牌傳遞
- 藍牙、FDDI、令牌環網
9 局域網
9.1 ARP協議
9.1.1 ARP協議簡介
- 32位IP地址:
- 接口的網絡層地址
- 用于標識網絡層(第3層)分組，支持分組轉發
- MAC地址(或稱LAN地址,物理地址,以太網地址) :
- 作用：用于局域網內標識一個幀從哪個接口發出，到達哪個物理相連的其他接口
- 48位MAC地址(用于大部分LANs)，固化在網卡的 ROM中，有時也可以軟件設置
- e.g.: 1A-2F-BB-76-09-AD
以十六進制表示。
- 局域網中的每塊網卡都有一個唯一的MAC 地址
- MAC地址由IEEE統一管理與分配
- 網卡生產商購買MAC地址空間(前24比特)
- 類比：
- MAC地址：身份證號
- IP地址：郵政地址
- MAC地址是“平面”地址： ? 可“攜帶”
- 可以從一個LAN移到另一個LAN
- IP地址是層次地址： ? 不可“攜帶”
- IP地址依賴于結點連接到哪個子網
9.1.2 ARP: 地址解析協議
9.1.3 ARP協議在同一局域網內的工作機制（尋址）
- A想要給同一局域網內的B發送數據報
- B的MAC地址不在A的ARP表中.
- A廣播ARP查詢分組，其中包含B的IP地址
- 目的MAC地址 = FF-FFFF-FF-FF-FF
- LAN中所有結點都會接收ARP查詢
- B接收ARP查詢分組，IP地址匹配成功，向A應答B的MAC地址
- 利用單播幀向A發送應答
- A在其ARP表中，緩存B的IP-MAC地址對，直至超時
- 超時后，再次刷新
- ARP是“即插即用”協議:
- 結點自主創建ARP表， 無需干預
本小節是在同一個LAN中ARP工作機制，下一小節講跨LAN時ARP工作機制。
9.1.4 ARP協議在不同局域網間的工作機制（尋址）
- 通信過程: A通過路由器R向B發送數據報
- 關注尋址：IP地址(數據報中)和MAC地址(幀中)
- 假設A知道B的IP地址(怎么知道的?)
- 假設A知道第一跳路由器R (左)接口IP地址 (怎么知道的?)
- 假設A知道第一跳路由器R (左)接口MAC地址 (怎么知道的?)
A是如何確定要把數據發送到R的左邊接口的？
默認網關,也稱“第一跳路由器”。
- 在上圖中，A將分組發往B的過程詳解：
- A構造IP數據報，其中源IP地址是A的IP地址，目的IP地址是B的IP地址
- A構造鏈路層幀，其中源MAC地址是A的MAC地址，目的MAC地址是R(左)接口的MAC地址，封裝A到B的IP數據報。
- 幀從A發送至R
- R接收幀，提取IP數據報，傳遞給上層IP協議
- R轉發IP數據報（源和目的IP地址不變！）
- R創建鏈路層幀，其中源MAC地址是R(右)接口的MAC地址，目 的MAC地址是B的MAC地址，封裝A到B的IP數據報。
- R轉發IP數據報（源和目的IP地址不變！）
- R創建鏈路層幀，其中源MAC地址是R (右)接口的MAC地址，目的MAC地址是B的MAC地址，封裝A到B的IP數據報。
通過上面過程，可以發現IP src和IP dest是不會改變的，因為在網絡層將數據報遞交給鏈路層時數據報會被封裝起來。
9.2 以太網
何為以太？
以太是古希臘哲學家亞里士多德所設想的一種物質。是物理學史上一種假想的物質觀念，其內涵隨物理學發展而演變。“以太”一詞是英文Ether或Aether的音譯。古希臘人以其泛指青天或上層大氣。在亞里士多德看來，物質元素除了水、火、氣、土之外，還有一種居于天空上層的以太。在科學史上，它起初帶有一種神秘色彩。后來人們逐漸增加其內涵，使它成為某些歷史時期物理學家賴以思考的假想物質。
以太是古希臘哲學家亞里士多德所設想的一種物質。19世紀的物理學家，認為它是一種曾被假想的電磁波的傳播媒質。但后來的實驗和理論表明，如果假定“以太”的不存在，很多物理現象可以有更為簡單的解釋。
9.2.1 以太網
- “統治地位”的有線LAN技術:
- 造價低廉(NIC不足￥100.00)
- 應用最廣泛的LAN技術
- 比令牌局域網和ATM等，簡單、便宜
- 滿足網絡速率需求：10 Mbps – 10 Gbps
以太網：物理拓撲
- 總線(bus): 上世紀90年代中期前流行
- 所有結點在同一沖突域(collision domain) (可能彼此沖突)
- 星型(star): 目前主流網絡拓撲
- 中心交換機(switch)
- 每個結點一個單獨沖突域(結點間彼此不沖突)
以太網：不可靠、無連接服務
- 無連接(connectionless): 發送幀的網卡與接 收幀的網卡間沒有“握手”過程
- 不可靠(unreliable): 接收網卡不向發送網卡進行確認
- 差錯幀直接丟棄，丟棄幀中的數據恢復依靠高 層協議 (e.g., TCP)，否則，發生數據丟失
- 以太網的MAC協議: 采用二進制指數退避算 法的CSMA/CD
以太網CSMA/CD算法
- 第m次連續沖突后：
? 取n = Min(m, 10)
? NIC 從{0,1,2, …, 2n-1}中隨機選擇一個數K
? NIC等待K?512比特的傳輸 延遲時間，再返回第2步 - 連續沖突次數越多，平均等待時間越長。
以太網幀結構
發送端網卡將IP數據報(或其他網絡層協議分組)封裝到以太網幀中：
- 前導碼(Preamble)(8B):
- 7個字節的10101010，第8字節為10101011
- 用于發送端與接收端的時鐘同步
- 目的MAC地址、源MAC地址(各6B):
- 如果網卡的MAC地址與收到的幀的目的MAC地址匹配，或者幀的目的MAC地址為廣播地址(FF-FF-FF-FF-FF-FF)，則網卡接收該幀，并將其封裝的網絡層分組交給相應的網絡層協議。
- 否則，網卡丟棄(不接收)該幀。
- 類型(Type)(2B):
指示幀中封裝的是哪種高層協議的分組 (如，IP數據報、Novell IPX數據報、AppleTalk數據報等) - 數據(Data)(46-1500B):
指上層協議載荷。- R=10Mbps，RTTmax=512μs，Lmin / R = RTTmax
- Lmin=512bits=64B，Datamin=Lmin-18=46B
- CRC(4B): 循環冗余校驗碼
- 丟棄差錯幀
- 丟棄差錯幀
802.3以太網標準: 鏈路與物理層
- 許多不同的以太網標準
- 相同的MAC協議和幀格式
- 不同速率: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps
- 不同物理介質: 光纖, 線纜
科普：何為雙絞線？
雙絞線（twisted pair，TP）是一種綜合布線工程中最常用的傳輸介質，是由兩根具有絕緣保護層的銅導線組成的。把兩根絕緣的銅導線按一定密度互相絞在一起，每一根導線在傳輸中輻射出來的電波會被另一根線上發出的電波抵消，有效降低信號干擾的程度。
雙絞線一般由兩根22～26號絕緣銅導線相互纏繞而成，“雙絞線”的名字也是由此而來。實際使用時，雙絞線是由多對雙絞線一起包在一個絕緣電纜套管里的。如果把一對或多對雙絞線放在一個絕緣套管中便成了雙絞線電纜 ，但日常生活中一般把“雙絞線電纜”直接稱為“雙絞線”。
與其他傳輸介質相比，雙絞線在傳輸距離，信道寬度和數據傳輸速度等方面均受到一定限制，但價格較為低廉。
- 原理
雙絞線是由一對相互絕緣的金屬導線絞合而成。采用這種方式，不僅可以抵御一部分來自外界的電磁波干擾，也可以降低多對絞線之間的相互干擾。把兩根絕緣的導線互相絞在一起，干擾信號作用在這兩根相互絞纏在一起的導線上是一致的（這個干擾信號叫做共模信號），在接收信號的差分電路中可以將共模信號消除，從而提取出有用信號（差模信號） 。
9.2.2 交換機
- 鏈路層設備
- 存儲-轉發以太網幀
- 檢驗到達幀的目的MAC地址，選擇性 (selectively) 向一個或多個輸出鏈路轉發幀
- 利用CSMA/CD訪問鏈路，發送幀
- 透明(transparent)
- 主機感知不到交換機的存在
- 即插即用(plug-and-play)
- 自學習(self-learning)
- 交換機無需配置
交換機: 多端口間同時傳輸
注意：下面的圖中用英文字母簡單代替MAC地址以便描述。
- 主機利用獨享(dedicated) 鏈路直接連接交換機
- 交換機緩存幀
- 交換機在每段鏈路上利用 CSMA/CD收發幀，但無 沖突，且可以全雙工
- 每段鏈路一個獨立的沖突域
- 交換(switching):A-A’與 B-B’的傳輸可以同時進行，沒有沖突
交換機轉發表：交換表
Q: 交換機怎么知道A’可以通過接口4到達，而B’可以通過接口5 到達?
- A: 每個交換機有一個交換表 (switch table), 每個入口(entry):
- (主機的MAC地址, 到達主機的接 口, 時間戳)
- 看起來很像路由表！
- Q: 交換表入口信息如何創建和 維護的那？
- 類似于路由協議？
- 類似于路由協議？
交換機: 自學習
- 交換機通過自學習，獲知到達主機的接口信息
- 當收到幀時，交換機“學習”到發送幀的主機（通 過幀的源MAC地址），位于收到該幀的接口所連接 的LAN網段
- 將發送主機MAC地址/接口信息記錄到交換表中
交換機: 幀過濾/轉發
當交換機收到幀:
自學習與轉發過程舉例
- 目的MAC地址A’，位置未知： 泛洪
- 目的MAC地址A，位置已知： 選擇性轉發
交換機互聯
- 交換機可以互聯
Q:當A向G發送幀時，S1怎么知道通過S4轉發？S4又怎么 知道通過S3轉發?
A: 自學習！(工作過程與單一交換機情形相同！) (通過泛洪自學習。)
多交換機自學習舉例
假設C向H發送幀，H向C發送應答幀
Q:請給出S1, S2, S3, S4的交換表，并說明幀的轉發過程?
組織機構(Institutional)網絡
9.2.3 交換機 vs. 路由器
兩者均為存儲-轉發設備:
- 路由器: 網絡層設備 (檢測 網絡層分組首部)
- 交換機: 鏈路層設備 (檢測 鏈路層幀的首部)
二者均使用轉發表:
- 路由器: 利用路由算法(路 由協議)計算(設置), 依據IP地址
- 交換機: 利用自學習、泛洪 構建轉發表, 依據MAC地址
9.2.4 網絡設備對比
所謂 直通傳輸 指的是邊收邊發。
9.2.5 虛擬局域網(VLAN)
VLANs的研發動機
考慮一下情形:
- CS用戶遷移到EE，但是希望連接至CS交換機， 怎么辦？
- 單一廣播域:
- 所有第2層廣播流量(ARP, DHCP, 未知目的MAC地址 位置)必須穿越整個LAN
- 安全/隱私、效率問題
VLANs
基于端口的VLAN
- 流量隔離(traffic isolation): 去往/來自端口1-8的幀只到達端口1-8
- 也可以基于MAC地址定義 VLAN, 而不是交換端口
- 動態成員: 端口可以動態分 配給不同VLAN
路由器 - 在VLAN間轉發: 通過路由(就像在 獨立的交換機之間) 實踐中，廠家會將交換機與路由器集成在一起
跨越多交換機的VLAN
- 多線纜連接
- 每個線纜連接一個VLAN
- 中繼端口(trunk port): 在跨越多個物理交換機定義的VLAN 承載幀
- 為多VLAN轉發802.1幀容易產生歧義 (必須攜帶VLAN ID信息)
- 802.1q協議為經過中繼端口轉發的幀增加/去除額外的首部域
802.1Q VLAN幀格式
9.3 PPP協議
9.3.1 點對點數據鏈路控制
- 一個發送端，一個接收端，一條鏈路：比廣播 鏈路容易
- 無需介質訪問控制(Media Access Control)
- 無需明確的MAC尋址
- e.g., 撥號鏈路, ISDN鏈路
- 常見的點對點數據鏈路控制協議：
- HDLC: High Level Data Link Control
- PPP (Point-to-Point Protocol)
9.3.2 PPP設計需求[RFC 1557]
- 組幀：將網絡層數據報封裝到數據鏈路層幀中
- 可以同時承載任何網絡層協議分組(不僅IP數據報)
- 可以向上層實現分用（多路分解）
- 比特透明傳輸：數據域必須支持承載任何比特 模式
- 差錯檢測：(無糾正)
- 連接活性(connection liveness)檢測：檢測、并 向網絡層通知鏈路失效
- 網絡層地址協商：端結點可以學習/配置彼此網 絡地址
9.3.3 PPP無需支持的功能
- 無需差錯糾正/恢復
- 無需流量控制
- 不存在亂序交付
- 無需支持多點鏈路
9.3.4 PPP數據幀
- 標志(Flag): 定界符(delimiter)
- 地址(Address): 無效(僅僅是一個選項)
- 控制(Control): 無效；未來可能的多種控制域
- 協議(Protocol): 上層協議 (eg, PPP-LCP, IP, IPCP, etc)
- 信息(info): 上層協議分組數據
- 校驗(check): CRC校驗，用于差錯檢測
9.3.5 字節填充(Byte Stuffing)
- “數據透明傳輸”需求: 數據域必須允許包含標志模式<01111110>
- Q: 如何判斷該作為數據接收，還是作為標志處理？
- 發送端: 在數據中的<01111110>和 <01111101>字節前添加額外的字節 <01111101> (“填充(stuffs)”)
- 接收端:
- 單個字節<01111101>表示一個填充字節
- 連續兩個字節<01111101>：丟棄第1個，第2個作為數據接收
- 單個字節<01111110>: 標志字節
- <01111110><01111101>字節表示此時的<01111110>是數據而不是標志
9.3.6 PPP數據控制協議
在交換網絡層數據之前，PPP數據鏈路兩端必須：
- 配置PPP鏈路
- 最大幀長
- 身份認證(authentication)
- etc.
- 學習/配置網絡層信息
- 對于IP協議: 通過交換IPCP 協議 (IP Control Protocol ) 報文 (IP分組首部的“上層 協議”字段取值: 8021)，完成IP地址等相關信息配置
- PPP協議狀態：
9.4 802.11無線局域網
9.4.1 IEEE 802.11無線局域網
- 802.11b
- 2.4-2.5GHz免費頻段 (unlicensed spectrum)
- 最高速率：11 Mbps
- 物理層采用直接序列擴頻 (DSSS)技術
- 所有主機使用相同的碼 片序列
- 802.11a
- 5-6 GHz頻段
- 最高速率：54 Mbps
- 802.11g
- 2.4-2.5 GHz頻段
- 最高速率：54 Mbps
- 802.11n: 多天線(MIMO)
- 2.4-2.5 GHz頻段
- 最高速率：600 Mbps
9.4.2 IEEE 802.11體系結構
- 無線主機與基站通信
- 基站(base station) = 訪問點(access point-AP)
- 基本服務集BSS(Basic Service Set)，也稱為單元(cell)
- 基礎設施網絡模式: ?
- 無線主機
- AP: 基站
- 基礎設施網絡模式: ?
- 自組網(ad hoc)模式:
- 只有主機
9.4.3 802.11：信道與AP關聯
- 802.11b: 2.4GHz-2.485GHz頻譜劃分為11個不同 頻率的信道
- 每個AP選擇一個頻率(信道)
- 存在干擾可能: 相鄰的AP可能選擇相同的信道！
- 主機: 必須與某個AP關聯(associate)
- 掃描信道，監聽包含AP名稱(服務集標識符-SSID )和MAC地址的信標(beacon)幀
- 選擇一個AP進行關聯
- 可能需要進行身份認證
- 典型情形：運行DHCP獲取IP地址等信息
9.4.4 802.11AP關聯：被動掃描與主動掃描
- 被動掃描(scanning):
- 各AP發送信標幀
- 主機(H1)向選擇的AP發送關聯請求幀
- AP向主機(H1)發送關聯響應幀
- 主動掃描:
- 主機(H1)主動廣播探測請求幀 (Probe Request Frame)
- AP發送探測響應幀(Probe Response Frame)
- 主機(H1)向選擇的AP發送關聯請求幀
- AP向主機(H1)發送關聯響應幀
9.4.5 802.11：多路訪問控制
- 避免沖突: 2+結點同時傳輸
- 802.11: CSMA – 發送數據前監聽信道
- 避免與正在進行傳輸的其他結點沖突
- 802.11: 不能像CSMA/CD那樣，邊發送、邊檢測沖突！
- 無線信道很難實現
- 無法偵聽到所有可能的沖突：隱藏站、信號衰落
- 目標: 避免沖突(avoid collisions)-CSMA/C(ollision)A(voidance)
9.4.6 IEEE 802.11 MAC協議: CSMA/CA
-
802.11 sender
1
2
-
802.11 receiver
9.4.7 IEEE 802.11 MAC協議: CSMA/CA
基本思想：允許發送端“預約”(reserve)信道，而不是隨機發送數據幀，從而避免長數據幀的沖突。
- 發送端首先利用CSMA向BS發送一個很短的RTS (request-to-send)幀
- RTS幀仍然可能彼此沖突 (但RTS幀很短)
- BS廣播一個CTS(clear-to-send)幀作為對RTS的響應
- CTS幀可以被所有結點接收
- 消除隱藏站影響
- 發送端可以發送數據幀
- 其他結點推遲發送
9.4.8 沖突避免(CA): RTS-CTS交換
9.4.9 IEEE 802.11 MAC幀
- IEEE 802.11數據幀地址
上圖中的4個address。- 802.11數據幀有4個地址字段
- 地址4：用于自組網絡
- 地址1~地址3：
給一個例子說明地址1~地址3是如何起作用的：
總結
以上是生活随笔為你收集整理的计算机网络核心知识（中）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 作者：沈志宏（1977-），男，博士，中
- 下一篇： markdown编辑模式添加除水印图片方