第四章 網(wǎng)絡(luò)層

學習目的：

• 理解網(wǎng)絡(luò)層服務(wù)的主要原理
  • 網(wǎng)絡(luò)岑服務(wù)模型
  • 轉(zhuǎn)發(fā)（forwarding）和路由（routing）的概念對比
  • 路由器的工作原理
  • 路由算法及路由協(xié)議
• 完成簡單的組網(wǎng)及IP地址和路由配置

4.1 引言

網(wǎng)絡(luò)層提供的功能

• 從發(fā)送方主機傳輸報文段到接收方主機
• 發(fā)送方主機封裝報文段（segments）為**數(shù)據(jù)報（datagrams) **
• 接收方主機遞交報文段給傳輸層
• 在每個主機、路由器都需要運行網(wǎng)絡(luò)層協(xié)議
• 路由器會檢查通過它的所有IP的數(shù)據(jù)報的頭部字段，然后根據(jù)目標IP地址對數(shù)據(jù)報進行轉(zhuǎn)發(fā)

兩個主要的網(wǎng)絡(luò)層功能

• 轉(zhuǎn)發(fā)(forwarding): 將分組從路由器的輸入端口轉(zhuǎn)移到正確的路由器輸出端口（的路由器本地動作）
  • 類似駕車通過一個立交橋
• 路由(routing): 確定分組從發(fā)送方傳輸?shù)浇邮辗?目的主機)所經(jīng)過的路徑(或路由)
  • 路由算法
  • 雷系從發(fā)送方到接收方規(guī)劃旅行路線的過程

路由與轉(zhuǎn)發(fā)的相互作用

網(wǎng)絡(luò)層：數(shù)據(jù)平面和控制平面

數(shù)據(jù)平面

• 本地的，每個路由器自身的功能
• 決定抵達路由器輸入端口的數(shù)據(jù)包如何轉(zhuǎn)發(fā)到輸出端口

控制平面

• 整個網(wǎng)絡(luò)范圍
• 決定數(shù)據(jù)報在端到端路徑上的路由器之間如何路由
• 兩種數(shù)據(jù)平面的實現(xiàn)方式：
  • 傳統(tǒng)的路由算法: 在路由器內(nèi)實現(xiàn)
  • 軟件定義網(wǎng)絡(luò)（software-defined networking, SDN): 在遠程服務(wù)器上實現(xiàn)
• 控制平面：傳統(tǒng)方式
  • 每個路由器都有單獨的路由算法組件，路由器之間通過交互來實現(xiàn)控制平面
• 控制平面：SDN方法
  • 一個分離的（通常是遠程的）控制器和路由器本地的控制代理 (local control agents，CAs) 交互
  • CA一般擁有最少的功能，其任務(wù)是與控制器通信并且按控制器命令行事。
  • CA既不能直接交互，也不能主動參與計算轉(zhuǎn)發(fā)表

連接建立*

• 傳輸層連接: 如TCP協(xié)議，在數(shù)據(jù)實際傳輸之前，需要發(fā)送方和接收方經(jīng)過三次握手建立所需的狀態(tài)信息。兩個進程之間建立連接
• 網(wǎng)絡(luò)層連接: 指網(wǎng)絡(luò)層數(shù)據(jù)分組開始傳輸前，在所選擇的從源到目的地路徑上的各路由器之間相互握手，建立連接狀態(tài)。
  如ATM、幀中繼、MPLS的網(wǎng)絡(luò)層。（已經(jīng)很少使用）
  如今的因特網(wǎng)網(wǎng)絡(luò)層不執(zhí)行連接建立。

網(wǎng)絡(luò)層的服務(wù)模型-定義了分組在發(fā)送與接收端之間的端到端的 運輸特性

問題: 什么樣的服務(wù)模型可以用于將數(shù)據(jù)報從發(fā)送方傳輸?shù)浇邮辗剑?/p>

網(wǎng)絡(luò)層可能提供的服務(wù)

• 確保交付：確保分組到達目的地。
• 具有時延上界的確保交付：主機到主機的時延。
• 有序分組交付：按發(fā)送順序到達。
• 確保最小帶寬：當發(fā)送主機以低于特定比特率的速率發(fā)送比特，分組不會丟失，在一定時延到達。
• 確保最大時延抖動：發(fā)送方發(fā)送兩個連續(xù)分組的時間間隔與接收到的間隔相同。

因特網(wǎng)的網(wǎng)絡(luò)層提供的服務(wù)

• 單一服務(wù)，即盡力而為服務(wù)(best-effort service) 。
• 分組間的定時不能被保證；
• 分組的接收順序與發(fā)送順序不一定相同；
• 傳送的分組不能保證最終交付，即網(wǎng)絡(luò)可能未向目的地交付分組。

4.2 虛電路和數(shù)據(jù)報網(wǎng)絡(luò)

連接和無連接服務(wù)

• 數(shù)據(jù)報 網(wǎng)絡(luò)提供網(wǎng)絡(luò)層的無連接 服務(wù)
• 虛電路 網(wǎng)絡(luò)提供網(wǎng)絡(luò)層的 連接 服務(wù)
• 類比于TCP/UDP的面向連接/ 無連接的傳輸層服務(wù)：
  • 任何網(wǎng)絡(luò)中的網(wǎng)絡(luò)層只提供兩種服務(wù)之一，不會同時提供。
    • 虛電路網(wǎng)絡(luò)：提供連接服務(wù)。
    • 數(shù)據(jù)報網(wǎng)絡(luò)：提供無連接服務(wù)。
• 傳輸層：面向連接服務(wù)在網(wǎng)絡(luò)邊緣的端系統(tǒng)中實現(xiàn)。
• 網(wǎng)絡(luò)層：面向連接服務(wù)在端系統(tǒng)及網(wǎng)絡(luò)核心的路由器中實現(xiàn)。

虛電路(Virtual Circuits)*

“源主機-目的主機路徑的行為類似于電話網(wǎng)絡(luò)的行為”

• 性能上類似

• 沿著源-目的路徑的網(wǎng)絡(luò)行為類似

• 在數(shù)據(jù)傳輸之前，需要為每個呼叫建立連接

• 每個分組攜帶VC標識符(不是目的主機地址)

• 位于“源-目的路徑”上的每個路由器會維護經(jīng)過它的每條連接的“狀態(tài)”

• 鏈路和路由器的資源(帶寬、緩存)可以被分配給VC(專用資源)

數(shù)據(jù)報網(wǎng)絡(luò)

• 在網(wǎng)絡(luò)層無呼叫的過程
• 路由器： 不需要維護端到端連接的狀態(tài)
• 沒有網(wǎng)絡(luò)等級的“連接”的概念
• 使用目的主機的地址進行分組轉(zhuǎn)發(fā)

數(shù)據(jù)報轉(zhuǎn)發(fā)表

路由器查表方法

• 用目的地址前綴與轉(zhuǎn)發(fā)表的前綴匹配：
• 存在匹配：向?qū)溌忿D(zhuǎn)發(fā)。
  如，目的地址
  11001000 00010111 00010110 10100001 ?
• 不存在匹配：選擇“其他”項對應的鏈路轉(zhuǎn)發(fā)。
• 存在多個匹配：使用最長前綴匹配規(guī)則，即向與最長前綴匹配的鏈路接口轉(zhuǎn)發(fā)分組。
  如，目的地址
  11001000 00010111 00011000 10101010 ?

說明

• 路由器轉(zhuǎn)發(fā)表只維持轉(zhuǎn)發(fā)狀態(tài)信息；
• 轉(zhuǎn)發(fā)表由選路算法修改（1～5分鐘更新）；虛電路網(wǎng)絡(luò)轉(zhuǎn)發(fā)表隨虛電路的建立和拆除更新。
• 一個端系統(tǒng)發(fā)送給另一個端系統(tǒng)的一批分組可能在網(wǎng)絡(luò)中選擇不同的路徑，到達的順序可能不一致。

虛電路網(wǎng)絡(luò)的特點*

虛電路網(wǎng)絡(luò)源于電話產(chǎn)業(yè)界（采用“真正”電路）。

• 呼叫建立及每次呼叫的狀態(tài)要在網(wǎng)絡(luò)中的路由器上維持，比面向數(shù)據(jù)報的網(wǎng)絡(luò)要復雜。
• 網(wǎng)絡(luò)功能復雜，端系統(tǒng)設(shè)備簡單

數(shù)據(jù)報網(wǎng)絡(luò)的特點

由互連計算機的需求發(fā)展而來。與電話網(wǎng)相反。

• 網(wǎng)絡(luò)層服務(wù)模型簡單。
• 端系統(tǒng)功能復雜：高層實現(xiàn)許多功能，如按序傳送、可靠數(shù)據(jù)傳輸、擁塞控制與DNS名字解析等；
• 帶來的結(jié)果
  • 因特網(wǎng)服務(wù)模型提供的服務(wù)保證最少（可能沒有?。瑢W(wǎng)絡(luò)層的需求最小，使得互連使用各種不同鏈路層技術(shù)的網(wǎng)絡(luò)變得更加容易。
• 許多應用都在位于網(wǎng)絡(luò)邊緣的主機（服務(wù)器）上實現(xiàn)。

4.3 路由器的工作原理

路由器的整體結(jié)構(gòu)

• 路由器的兩個核心功能：
  • 運行路由算法/協(xié)議(OSPF, RIP, BGP)
  • 將分組從路由器的輸入鏈路傳送到正確的輸出鏈路。
• 路由器的體系結(jié)構(gòu)：

輸入端口功能

• 第一個線路端接模塊：將一條物理鏈路端接到路由器的物理層；
• 第二個數(shù)據(jù)鏈路處理模塊：實現(xiàn)路由器的數(shù)據(jù)鏈路層功能；
• 第三個查找與轉(zhuǎn)發(fā)模塊：實現(xiàn)查找與轉(zhuǎn)發(fā)功能，以便分組通過路由器交換結(jié)構(gòu)轉(zhuǎn)發(fā)到適當?shù)妮敵龆丝冢?/li>

輸入端口——查找/轉(zhuǎn)發(fā)模塊

確定將一個到達的分組通過交換結(jié)構(gòu)轉(zhuǎn)發(fā)給哪個輸出端口。 通過查找轉(zhuǎn)發(fā)表實現(xiàn)，這里的轉(zhuǎn)發(fā)表是存儲在輸入端口的內(nèi)存中。

• 分布式交換：
• 選路處理器計算轉(zhuǎn)發(fā)表，給每個輸入端口存放一份轉(zhuǎn)發(fā)表拷貝。
• 在每個輸入端口本地做出交換決策，無須激活中央選路處理器。
• 可避免在路由器中某個單點產(chǎn)生轉(zhuǎn)發(fā)處理瓶頸。
• 目的：以線速完成輸入端口的處理
• 排隊：如果數(shù)據(jù)報到達輸入端口的速度快于輸入端口將數(shù)據(jù)報轉(zhuǎn)發(fā)到交換結(jié)構(gòu)的速度，就會發(fā)生排隊

交換結(jié)構(gòu)

• 將分組從輸入端口緩存交換（轉(zhuǎn)發(fā)）到恰當?shù)妮敵龆丝诰彺嬷?/strong>
• 三種類型的交換結(jié)構(gòu)

• 早期用計算機作為路由器時采用的結(jié)構(gòu)(第一代)
• 輸入端口與輸出端口之間的交換由CPU(選路處理器)控制完成；
• 輸入端口與輸出端口類似I/O設(shè)備：
  • 當分組到達輸入端口時，通過中斷向選路處理器發(fā)出信號，將分組拷貝到處理器內(nèi)存中；
  • 選路處理器根據(jù)分組中的目的地址查表找出適當?shù)妮敵龆丝冢瑢?strong>該分組拷貝到輸出端口的緩存中。

轉(zhuǎn)發(fā)速度

交換速度受總線帶寬的速度限制 (每個分組穿過兩次總線)
若總線帶寬為每秒寫入或讀出B個分組，則總的轉(zhuǎn)發(fā)吞吐量 (分組從輸入端口被傳送到輸出端口的總速率)小于B/2。

不能同時轉(zhuǎn)發(fā)兩個分組，即使它們有不同的目的端口，因為經(jīng)過共享系統(tǒng)總線一次僅能執(zhí)行一個內(nèi)存讀寫

經(jīng)總線的交換結(jié)構(gòu)

輸入端口通過一條共享總線將分組直接傳送到輸出端口，不需要選路處理器的干預。

• 每次只能有一個分組通過總線傳送。
• 分組到達一個輸入端口時，若總線正忙，會被暫時阻塞，在輸入端口排隊
• 路由器交換帶寬受總線速率限制。

經(jīng)交換矩陣交換結(jié)構(gòu)

• 縱橫式交換機：由2n 條總線組成，n 個輸入端口與n 個輸出端口連接。
• 到達輸入端口的分組沿水平總線穿行，直至與所希望的輸出端口的垂直總線交叉點：
• 若該條垂直總線空閑，則分組被傳送到輸出端口；
• 否則，該到達的分組被阻塞，必須在輸入端口排隊。

輸出端口

• 取出存放在輸出端口內(nèi)存中的分組，并將其傳輸?shù)捷敵鲦溌飞稀?/li>
• 當交換結(jié)構(gòu)將分組交付給輸出端口的速率超過輸出鏈路速率，就需要排隊與緩存管理功能。當輸出端口的緩沖區(qū)溢出時，就會出現(xiàn)延時和丟包。

輸出端口排隊

• 當經(jīng)過交換結(jié)構(gòu)到達的速度超過了輸出端口的處理線速就會發(fā)生排隊
• 當輸出端口的緩沖區(qū)溢出時就會發(fā)生丟包！
• 當交換結(jié)構(gòu)的速度慢于輸入端口的速度，就會在輸入端口的緩沖區(qū)發(fā)生排隊
  會導致排隊延時和由于輸入緩沖區(qū)溢出導致的丟包！
• 線頭阻塞（Head-of-the-Line (HOL) blocking）: 在隊列前面的被阻塞的數(shù)據(jù)報會阻止隊列中的其他數(shù)據(jù)報被轉(zhuǎn)發(fā)。

4.4 網(wǎng)際協(xié)議：因特網(wǎng)中的轉(zhuǎn)發(fā)和編址

因特網(wǎng)中的網(wǎng)絡(luò)層協(xié)議

IP 數(shù)據(jù)報格式（IPv4）

數(shù)據(jù)報長度：是IP數(shù)據(jù)報的總長度，以字節(jié)計。長度為16比特，故數(shù)據(jù)報理論最大長度為65535字節(jié)。

高層協(xié)議：**通常僅當IP數(shù)據(jù)報到達最終目的地的時候才有用。**指示了IP數(shù)據(jù)報的數(shù)據(jù)部分應該交給哪個特定的運輸層協(xié)議。

協(xié)議號是網(wǎng)絡(luò)層與運輸層的粘合劑，而端口號是運輸層和應用層的粘合劑

首部校驗和：用于幫助路由器檢測收到的IP數(shù)據(jù)報中的比特錯誤

• 為什么TCP/IP在運輸層和網(wǎng)絡(luò)層都執(zhí)行差錯檢驗？
  • IP只對IP首部進行了差錯檢驗，而TCP/UDP是對整個TCp/UDP報文段進行的
  • 其次，TCP/UDP和IP不一定都屬于同一個協(xié)議棧。原則上，TCP能夠運行在一個不同的協(xié)議（如ATM）上，而IP能夠攜帶不一定要傳遞給TCP/UDP的數(shù)據(jù)

數(shù)據(jù)（有效載荷）: IP數(shù)據(jù)報中的數(shù)據(jù)字段包含要交付給目的地的運輸層報文段，當然也可承載其他類型數(shù)據(jù)，如ICMP報文段

注意到一個IP數(shù)據(jù)報有20字節(jié)的首部（假設(shè)無選項）。如果一個數(shù)據(jù)報承載著TCP報文段，則每個數(shù)據(jù)報共承載了40字節(jié) 的首部以及應用層報文

IP數(shù)據(jù)報分片和重組

• 每個數(shù)據(jù)鏈路有自己的MTU，鏈路類型不同，MTU的值也不同，這里MTU指的是數(shù)據(jù)鏈路幀的數(shù)據(jù)區(qū)的最大字節(jié)數(shù)
  • MTU：一個數(shù)據(jù)鏈路層幀能承載的最大數(shù)據(jù)量
• 在因特網(wǎng)中，一個大的分組可能在路由器中被分割為幾個分片，在最終的目的主機上，將這些分片重新組裝成一個大的分組
• 為了進一步識別出這些分組，需要對分片進行標識

分片的例子

偏移量要除以8，片偏移以八個字節(jié)為單位

IP地址

• IP 地址: 分配給主機或路由器接口的標識符
• 接口: 主機/路由器與物理鏈路之間的邊界
  • 路由器有多個接口
  • 主機可以有多個接口
  • 每個接口有一個IP地址
• IP地址有兩種：IPV4和IPV6
  • IPV4：32個二進制位長（4字節(jié)），常用點分十進制表示；
  • IPV6：128個二進制位長（16字節(jié)）常用冒號分隔表示

IPv4編址

• 32比特的二進制表示和點分十進制表示法
  • 將4個字節(jié)中的每一個字節(jié)分別用十進制數(shù)來表示，4個十進制數(shù)之間用 “.” 分隔。

如

根據(jù)不同的取值范圍，早期將IP地址分為五類。IP地址中前5位用于標識IP地址的類別，A類地址的第一位為“0”，B類地址的前兩位為“10”，C類地址的前三位為“110”，D類地址的前四位為“1110”，E類地址的前五位為“11110”。其中，A類、B類與C類地址為基本的IP地址。

IP地址結(jié)構(gòu)

包括兩部分：

• 網(wǎng)絡(luò)號：指明主機所在網(wǎng)絡(luò)的編號。
• 主機號：主機在網(wǎng)絡(luò)中的編號。

傳統(tǒng)的IP地址分類

A類地址

• 利用IP地址的第一個字節(jié)作為網(wǎng)絡(luò)地址，最高位為0，其余的三個字節(jié)作為主機地址。
  地址范圍為 1. 0. 0. 1－127.255.255.254
  注：全0表示本地地址，全1表示在本地網(wǎng)絡(luò)中向所有機廣播。

B類地址

• 利用IP地址的前兩個字節(jié)作為網(wǎng)絡(luò)地址，最高位為10，其余的兩個字節(jié)作為主機地址
  地址范圍為 128.0.0.1－191.255.255.254

C類地址

• 利用IP地址的前三個字節(jié)作為網(wǎng)絡(luò)地址，最高位為110，最后一個字節(jié)作為主機地址
  地址范圍為 192.0.0.1－223.255.255.254

特殊IP地址段

• 本地回環(huán)地址
  127.0.0.1-127.255.255.254
  這是預留的一組IP地址，主要是用來識別主機本身的地址。也叫做“l(fā)ocalhost”，一般用來測試。

• 私有地址（Private address）
  10.x.x.x, 172.16.x.x-172.31.x.x, 192.168.x.x
  這三個地址段被稱為私有IP地址段，也就是局域網(wǎng)所使用的地址段，在公網(wǎng)上不能被路由

• 0.0.0.0
  這個地址嚴格上來說都不是真正意義上的IP地址。主要是用來標識不清楚的網(wǎng)絡(luò)和主機的。系統(tǒng)遇到無法識別的網(wǎng)絡(luò)或主機的時候會統(tǒng)一的歸納到這個地址

• 255.255.255.255
  這個地址是受限的廣播地址。主要指一個網(wǎng)段內(nèi)的所有主機

互聯(lián)網(wǎng)中的IP地址

• 同一局域網(wǎng)上的主機或路由器的IP地址中的網(wǎng)絡(luò)號必須相同
• 交換機互連的網(wǎng)絡(luò)仍然是一個局域網(wǎng)，只能有一個網(wǎng)絡(luò)號。
• 路由器總是具有兩個或兩個以上IP地址。
• 當兩個路由器直接相連時，在連線兩端的接口處，可以指明IP地址也可以不指明IP地址。

劃分子網(wǎng)

• IP 地址:
  • 網(wǎng)絡(luò)號 (高位 bits)
  • 主機號 (低位 bits)
• 網(wǎng)絡(luò)號相同的IP地址屬于同一個網(wǎng)絡(luò)。而網(wǎng)絡(luò)還可以劃分為若干子網(wǎng)（subnet）。
• 劃分子網(wǎng)的方法是從主機號借用若干個比特作為子網(wǎng)號，剩下的主機位為主機號。

子網(wǎng)的特點

• 什么是一個子網(wǎng) ?
  (從IP地址的觀點來看)
  • 設(shè)備接口的IP地址具有同樣的網(wǎng)絡(luò)部分
  • 沒有路由器的介入，物理上能夠相互到達

為了確定子網(wǎng)，分開主機和路由器的每個接口，產(chǎn)生幾個隔離的網(wǎng)絡(luò)島，使用接口端接這些隔離的網(wǎng)絡(luò)的端點。這些隔離的網(wǎng)絡(luò)中的每一個都叫子網(wǎng)

子網(wǎng)掩碼

• **子網(wǎng)號字段長度是可變的，**因此，為了確定子網(wǎng)地址，IP協(xié)議提供了子網(wǎng)掩碼的概念 。
• 子網(wǎng)掩碼用來確定網(wǎng)絡(luò)地址（包括網(wǎng)絡(luò)號和子網(wǎng)號）和主機地址的長度。子網(wǎng)掩碼長為32位比特，其中的1對應于IP地址中的網(wǎng)絡(luò)號和子網(wǎng)號，而子網(wǎng)掩碼中的0對應于主機號。

子網(wǎng)劃分技術(shù)

例：現(xiàn)有一個網(wǎng)段202.114.1.1－202.114.1.254，
（1）請寫出怎樣將這個網(wǎng)段劃分為2個、6個、14個子網(wǎng)；
（2）假設(shè)這些IP用于某公司?，F(xiàn)公司任一部門，最多有30臺機器，問應該怎樣劃分子網(wǎng)？如果有49臺機器又將怎樣劃分？
對(1)、(2)，請寫出子網(wǎng)所需要的位數(shù)、子網(wǎng)掩碼和子網(wǎng)號。

解答要點:
(1) .2個借1位，6個接3位，14個借4位;
(2).30小于32，故每個子網(wǎng)的主機號只需5位,因為2⁵=32；同理49臺機器的話，就需要6位，因為2⁶=64。

注意：對某個子網(wǎng)來說，主機號全0的地址不能用，它被用做表示該子網(wǎng)的子網(wǎng)號；主機號全1的也不能用，它用于本子網(wǎng)的廣播。因此每個子網(wǎng)所能容納的主機數(shù)是2^N-2，N是主機號位數(shù)。

使用子網(wǎng)掩碼的分組轉(zhuǎn)發(fā)

不劃分子網(wǎng)時，路由表只有兩項：目的網(wǎng)絡(luò)地址和下一跳地址，例如

使用子網(wǎng)劃分后，路由表中將包括三項：目的網(wǎng)絡(luò)地址、子網(wǎng)掩碼和下一跳地址，例如：

傳統(tǒng)IP分類方法的問題

• 一個A類的IP地址，可以有24bit用于分配主機地址，因此可以支持 2²⁴個主機，但是一個家庭或者組織往往不需要這么多的地址空間，造成浪費。
• 一個C類的IP地址，只有8bit用于分配主機地址，因此只能支持256個主機，又不太夠用。
• 因此，按傳統(tǒng)IP地址分類方式分配IP被CIDR技術(shù)取代

無分類域間路由(Classless Inter-Domain Routing，CIDR)

• CIDR消除了傳統(tǒng)的A類、B類和C類地址的概念。
• 使用斜線記法，又稱為CIDR記法來區(qū)分網(wǎng)絡(luò)前綴和主機號，
  • 即在IP地址后面加一個斜線“/”，斜線后面用一個數(shù)字指定網(wǎng)絡(luò)前綴的長度。
• CIDR將網(wǎng)絡(luò)前綴都相同的連續(xù)的IP地址組成“CIDR地址塊”。

構(gòu)造超網(wǎng)(superneting)

一個CIDR地址塊可以表示分類IP的多個分類地址，這種地址的聚合稱為路由聚合，又稱為構(gòu)造超網(wǎng)。

使用單個網(wǎng)絡(luò)前綴通知多個網(wǎng)絡(luò)的能力

CIDR 地址塊劃分舉例 -層次尋址: 路由聚合

子網(wǎng)劃分及CIDR練習

現(xiàn)有一公司已獲得網(wǎng)絡(luò)號為202.1.1.0/24,如果該公司有3個部門,
（1）如果第1個部門有60臺計算機，第二個部門有20臺計算機，第三個部門有16臺計算機，問如何分配地址?
（2）如果第1個部門有120臺計算機，第2個部門有60臺計算機，第3個部門有60臺計算機，使用上述方法可以分配地址嗎？使用CIDR方法如何分配地址?

11001010 00000001 00000001 00000000

分配部門1：11001010 00000001 00000001 00000000 > 202.1.1.0/26

分配部門2：11001010 00000001 00000001 01000000 > 202.1.1.64/27

分配部門3: 11001010 00000001 00000001 01100000 > 202.1.1.96/28

(2) 不能。部門地址數(shù)目不夠。

11001010 00000001 00000001 00000000 > 202.1.1.0/25

11001010 00000001 00000001 10000000 > 202.1.1.128/26

11001010 00000001 00000001 11000000 > 202.1.1.192/26

動態(tài)主機配置協(xié)議

問: 主機如何得到IP地址?

• 手工指定（保存在系統(tǒng)配置中）

  • Windows: 控制面板->網(wǎng)絡(luò)
  • UNIX/LINUX: 在/etc/rc.config中，可使用ifconfig命令配置

• DHCP: Dynamic Host Configuration Protocol

  • 自動從一個DHCP服務(wù)器得到IP地址
  • 方便靈活

• plug-and-play（即插即用）

• DHCP概述：

  • 主機廣播 “DHCP DISCOVER” 消息
  • DHCP 服務(wù)器用 “DHCP OFFER” 消息響應
  • 主機請求IP地址: “DHCP REQUEST” 消息
  • DHCP 服務(wù)器確認 “DHCP ACK/NACK” 消息
  • DHCP 終止租用期”DHCP RELEASE”消息

DHCP協(xié)議的工作流程

1. DHCP 服務(wù)器被動打開 UDP 端口 67，等待客戶端發(fā)來的報文。
2. DHCP 客戶從 UDP 端口 68，發(fā)送 DHCP 發(fā)現(xiàn)報文。
3. 凡收到 DHCP 發(fā)現(xiàn)報文的 DHCP 服務(wù)器，都發(fā)出 DHCP 提供報文，因此 DHCP 客戶，可能收到多個 DHCP 提供報文。
4. DHCP 客戶從幾個 DHCP 服務(wù)器中選擇，其中的一個，并向所選擇的 DHCP 服務(wù)器發(fā)送 DHCP 請求報文。
5. 被選擇的 DHCP 服務(wù)器發(fā)送確認報文DHCPACK，客戶進入已綁定狀態(tài)，并可開始使用得到的臨時 IP 地址了
   1. DHCP 客戶現(xiàn)在要根據(jù)服務(wù)器提供的租用期 T 設(shè)置兩個計時器 T1 和 T2，它們的超時時間分別是 0.5T 和 0.875T。當超時時間到就要請求更新租用期。
6. 租用期過了一半（T1 時間到），DHCP 發(fā)送請求報文 DHCPREQUEST 要求更新租用期。
7. DHCP 服務(wù)器若不同意，則發(fā)回否認報文DHCPNACK。這時 DHCP 客戶必須立即停止使用原來的 IP 地址，而必須重新申請 IP 地址（回到步驟2）
8. DHCP 服務(wù)器若同意，則發(fā)回確認報文DHCPACK。DHCP 客戶得到了新的租用期，重新設(shè)置計時器。
9. 若DHCP服務(wù)器不響應步驟6的請求報文DHCPREQUEST，則在租用期過了 87.5% 時，DHCP 客戶必須重新發(fā)送請求報文 DHCPREQUEST（重復步驟6），然后又繼續(xù)后面的步驟。
10. DHCP 客戶可隨時提前終止服務(wù)器所提供的租用期，這時只需向 DHCP 服務(wù)器發(fā)送釋放報文DHCPRELEASE即可。

DHCP報文格式*

OP：若是client送給server的封包，設(shè)為1，反向為2；
Htype：硬件類別，ethernet為1；
Hlen：硬件長度，ethernet為6；
Hops：若數(shù)據(jù)包需經(jīng)過router傳送，每站加1，若在同一網(wǎng)內(nèi)，為0；
Transaction ID：事務(wù)ID，是個隨機數(shù)，用于客戶和服務(wù)器之間匹配請求和相應消息；
Seconds：由用戶指定的時間，指開始地址獲取和更新進行后的時間；
Flags：從0-15bits，最左一bit為1時表示server將以廣播方式傳送封包給 client，其余尚未使用；
Ciaddr：用戶IP地址；
Yiaddr：客戶IP地址；
Siaddr：用于bootstrap過程中的IP地址；
Giaddr：轉(zhuǎn)發(fā)代理（網(wǎng)關(guān)）IP地址；
Chaddr：client的硬件地址；
Sname：可選server的名稱，以0x00結(jié)尾；
File：啟動文件名；
Options：，廠商標識，可選的參數(shù)字段

DHCP 客戶端-服務(wù)器場景

首先是客戶端廣播，DHCP服務(wù)器收到后會返回DHCP提供，此時會有多個請求?？蛻舳诉x擇一個發(fā)出DHCP請求，請求分配IP地址，然后DHCP服務(wù)器返回DHCPACK。

DHCP: 不僅獲得IP地址

• DHCP分配的不僅僅是IP地址，還可分配：
  • 客戶的第一跳路由器的地址（網(wǎng)關(guān)）
  • DNS服務(wù)器的IP地址或域名
  • 子網(wǎng)掩碼
• DHCP是應用層協(xié)議

組織機構(gòu)如何獲取IP 地址？

Q: 怎樣獲取IP地址中的網(wǎng)絡(luò)號部分？
A: 從ISP的地址空間中劃分一塊給申請者
例如：

• ISP獲得地址塊的方法——從ICANN獲取
  ICANN（Internet Corporation for Assigned Names and Numbers） http://www.icann.org/
  • 分配IP地址
  • 管理DNS
  • 分配域名，解決糾紛

NAT: 網(wǎng)絡(luò)地址轉(zhuǎn)換

• 動機: 對外部網(wǎng)絡(luò)來講，本地網(wǎng)絡(luò)只用一個IP地址
  • 不需要從 ISP分配一系列地址—— 只要一個IP地址用于所有設(shè)備
  • 在本地網(wǎng)絡(luò)，改變設(shè)備的IP地址不用通知外部世界
  • 可以變更 ISP ，不用改變本地網(wǎng)絡(luò)的設(shè)備的地址
  • 本地網(wǎng)絡(luò)內(nèi)部設(shè)備不能被外部世界明確尋址，或是不可見 (增加了安全性)

• 執(zhí)行NAT，路由器必須做到:
  • 外出的分組: 替換每個外出的分組的 (源IP 地址, 端口號) 為 (NAT IP 地址, 新端口號)
  • 遠程客戶/服務(wù)器用**(NAT IP地址, 新端口號)作為目的地**來響應。
  • (在NAT轉(zhuǎn)換表中)記錄每個(源IP 地址, 端口號)到 (NAT IP地址, 新端口號) 轉(zhuǎn)換配對
  • 進來的分組: 對每個進來的分組，用保存在NAT表中的對應的**(源IP 地址, 端口號)** 替換分組中的目的域 (NAT IP 地址, 新端口號）

網(wǎng)絡(luò)轉(zhuǎn)換的一些限制

• 16-bit 端口號:
  • 一個局域網(wǎng)地址可以同時支持60,000個并發(fā)連接!
• NAT 存在爭議
  • 路由器只應該處理到第三層
  • 違反了端到端主張
  • 應用程序設(shè)計者在設(shè)計時不得不將NAT加以考慮
  • 如P2P應用程序
  • 應使用IPv6來解決地址短缺問題

ICMP

(Internet Control Message Protocol，因特網(wǎng)控制報文協(xié)議）

• 用于主機路由器之間彼此交流網(wǎng)絡(luò)層信息
  • 差錯報告: 不可到達的主機, 網(wǎng)絡(luò),端口,協(xié)議
  • 請求/應答 (用于ping,traceroute)
• 位于IP之上
  • 因為ICMP消息是裝載在IP分組里的

ICMP報文格式及其封裝*

ICMP 報文類型及對應常見代碼*

Traceroute 和 ICMP

• 源端發(fā)送一系列的UDP分組給目的端
  • 第一個分組 TTL =1
  • 第二個 TTL=2, 等等
• 當?shù)趎個分組到達第n個路由器時
  • 路由器丟棄該分組
  • 并給源端發(fā)送一個ICMP報文 (type 11, code 0)
  • 這個報文包含了路由器的名稱和IP地址
• 當源端收到ICMP報文時，計算傳輸往返時間RTT
• 對每個TTL作三次
• 停止發(fā)送的依據(jù)：
  • UDP報文最終到達目的端
  • 目的端返回回應應答的 ICMP 報文 (type 3, code 3)
  • 源端停止發(fā)送

IPv6

• 初始動機：32-bit IPv4地址空間即將用盡
• 其他動機：
  • 首部格式可幫助加速處理/轉(zhuǎn)發(fā)
  • 改變首部利于QoS要求(Quality of service)
• IPv6 數(shù)據(jù)報格式
  • 固定長度的 40 字節(jié)首部
  • 不允許分片

IPv6首部*

• 優(yōu)先級: 表示流中分組的優(yōu)先級
• 流標識: 表示分組在同一個“流”中 (“流”的概念尚未完全定義)
• 下一個首部: 表示數(shù)據(jù)的上層協(xié)議

IPv6地址表示

• 冒號十六進制表示法
  例如：104.220.136.100.255.255.255.255.0.0.18.128.140.10.255.255
  用冒號十六進制表示為：
  69DC:8864:FFFF:FFFF:0:1280:8C0A:FFFF
• 零壓縮表示法
  例如：FF0C:0:0:0:0:0:B1
  零壓縮表示為：
  FF0C::B1

與IPv4的其它不同*

• 校驗和: 全部去掉，減少每一跳的處理時間
• ipv6不允許在中間路由器上進行分片與重新組裝。這種操作只能在源與目的地執(zhí)行。
• 選項: 允許, 但是不是標準首部的一部分，而是用下一個首部域指出
• ICMPv6:新版本的 ICMP
  • 增加消息類型, 例如“分組太大”
  • 多播組管理功能

從 IPv4 到 IPv6過渡*

• 并不是所有的路由器都能夠同時升級
  • 沒有 “標志日”
  • 同時有 IPv4 和 IPv6 路由器的網(wǎng)絡(luò)如何工作?
• 兩種推薦方法:
  • 雙棧：一些路由器具有雙重棧 (v6, v4) 能夠在兩種格式中轉(zhuǎn)換
  • 隧道: 在穿過IPv4路由器時，IPv6分組作為 IPv4分組的負載

雙棧方法*

隧道方法*

4.5 路由和選路

4.5.1選路算法

路由與轉(zhuǎn)發(fā)的相互作用

• 路由算法確定了通過網(wǎng)絡(luò)的端到端路徑
• 轉(zhuǎn)發(fā)表確定了在路由器上的本地轉(zhuǎn)發(fā)

路由的基本概念

• 默認路由器：與主機直接相連的路由器，又叫第一跳路由器。每當主機發(fā)送一個分組時，都先傳送給它的默認路由器。
  • 源路由器：源主機的默認路由器。
  • 目的路由器：目的主機的默認路由器。
  • 從源主機到目的主機的選路歸結(jié)為從源路由器到目的路由器的選路。
• 路由算法：是確定一個分組從源路由器到目的路由器所經(jīng)路徑的算法

找到一個子網(wǎng)到另一個子網(wǎng)的路徑

• 路由:按照某種指標(傳輸延遲,所經(jīng)過的站點數(shù)目等)找到一條

• 從源節(jié)點到目標節(jié)點的較好路徑

• 較好路徑: 按照某種指標較小的路徑

  • 指標:站數(shù), 延遲,費用,隊列長度等, 或者是一些單純指標的加權(quán)平均
  • 采用什么樣的指標,表示網(wǎng)絡(luò)使用者希望網(wǎng)絡(luò)在什么方面表現(xiàn)突出,什么指標網(wǎng)絡(luò)使用者比較重視

• 路由算法的關(guān)鍵：在給定的一組路由器以及連接路由器的鏈路中，找到一條從源路由器到目的路由器的“好”路徑。

網(wǎng)絡(luò)的抽象圖模型

• 用“節(jié)點圖”表示網(wǎng)絡(luò)的結(jié)構(gòu)
• 圖G = (N，E)表示N 個節(jié)點和E 條邊的集合，每條邊是來自N的一對節(jié)點。
• 節(jié)點：表示路由器(做出分組轉(zhuǎn)發(fā)判決的點)。
  如u，v，w，x，y，z。
• 邊：連接節(jié)點的線段，表示路由器之間的物理鏈路。
  如(u，v)、 (u，x) 、(u，w)、…

圖抽象在其他的網(wǎng)絡(luò)場景也受用，節(jié)點：peer，邊：TCP連接

網(wǎng)絡(luò)的抽象圖模型：費用(cost)

• Cost可以表示對應鏈路的物理長度、或鏈路速度、或與鏈路相關(guān)的費用。
• 定義：c(x，y) 表示節(jié)點 x 和節(jié)點 y 之間邊的費用（從節(jié)點 x 到節(jié)點 y 的鏈路費用）。
• 若節(jié)點x與節(jié)點y直接相連（x與y是鄰居）
  則c(x，y )= 鏈路費用
  如c(u，v) = 2，節(jié)點u與節(jié)點v互為鄰居
• 若節(jié)點x與節(jié)點y不直接相連（x與y不是鄰居）
  則c(x，y) = ∞
  如c(u，y) = ∞，c(u，z) = ∞
• c(x，y)= c(y，x)
  如c(u，v) = c(v，u) =2

最優(yōu)化原則(optimality principle)

• 匯集樹(sink tree)
  • 此節(jié)點到所有其它節(jié)點的最優(yōu)路徑形成的樹
  • 路由選擇算法就是為所有路由器找到并使用匯集樹

路由選擇算法原則

• 路由選擇算法的原則
• 正確性(correctness):算法必須是正確的和完整的,使分組一站一站接力，正確發(fā)向目標站；完整：目標所有的站地址，在路由表中都能找到相應的表項；沒有處理不了的目標站地址；
• 簡單性(simplicity):算法在計算機上應簡單：最優(yōu)但復雜的算法，時間上延遲很大，不實用，不應為了獲取路由信息增加很多的通信量；
• 健壯性(robustness):算法應能適應通信量和網(wǎng)絡(luò)拓撲的變化：通信量變化，網(wǎng)絡(luò)拓撲的變化算法能很快適應；不向很擁擠的鏈路發(fā)數(shù)據(jù)，不向斷了的鏈路發(fā)送數(shù)據(jù)
• 穩(wěn)定性(stability)：產(chǎn)生的路由不應該搖擺
• 公平性(fairness)：對每一個站點都公平
• 最優(yōu)性(optimality)：某一個指標的最優(yōu)，時間上，費用上，等指標，或綜合指標；實際上，獲取最優(yōu)的結(jié)果代價較高，可以是次優(yōu)的

路由算法分類

• 全局路由算法：所有路由器擁有完整的網(wǎng)絡(luò)拓撲信息和鏈路費用信息。

  • 鏈路狀態(tài)路由算法LS：必須知道網(wǎng)絡(luò)中每條鏈路的費用。

• 分布式路由算法：以迭代的、分布式的方式計算最低費用路徑。

  • 節(jié)點只有與其直接相連鏈路的費用信息：不需擁有所有網(wǎng)絡(luò)鏈路費用的完整信息。
  • 通過迭代計算，并與相鄰節(jié)點(鄰居節(jié)點)交換信息
  • 逐步計算出到達某目的節(jié)點或一組目的節(jié)點的最低費用路徑。
  • 距離向量路由算法DV：每個節(jié)點維護到網(wǎng)絡(luò)中所有其他節(jié)點的費用（距離）的估計向量。

• 靜態(tài)路由算法：

  • 路由確定后基本不再變化。只有人工干預調(diào)整時，可能有一些變化。

• 動態(tài)路由算法：

  • 當網(wǎng)絡(luò)的流量負載或拓撲發(fā)生變化時，路徑可能發(fā)生改變。
  • 可以周期性地或直接地響應拓撲或鏈路費用的變化。
  • 易受選路循環(huán)、路由振蕩之類問題的影響。

鏈路狀態(tài)選路算法Link state

將任何一個節(jié)點的鏈路狀態(tài)分組泛洪

• 第五步才是路由算法，前面都是測量和散播路由信息。

Dijkstra最低費用路徑算法

• 所有節(jié)點知道網(wǎng)絡(luò)拓撲，以及每條鏈路的費用信息
  • 通過鏈路狀態(tài)廣播來實現(xiàn)
  • 所有節(jié)點擁有相同的信息
• 計算任意一個節(jié)點（源節(jié)點）到所有其他節(jié)點的最低費用路徑
  • 給出該節(jié)點的轉(zhuǎn)發(fā)表
• 迭代：通過k次迭代后可以知道到達k個目的節(jié)點的最低費用路徑
• 基本思想：以源節(jié)點為起點，每次找出一個到源節(jié)點的費用最低的節(jié)點，直到把所有的目的節(jié)點都找到為止。
• 術(shù)語定義
  c(x,y)：表示從節(jié)點x到y(tǒng)的鏈路費用;
  = ∞ 如果不是直接鄰居
  D(v)：表示從源節(jié)點到目的節(jié)點v的當前路徑的費用；
  p(v)：表示從源節(jié)點到目的節(jié)點v的路徑上的前驅(qū)節(jié)點(例如w是v的前驅(qū)節(jié)點)；
  N’：表示已經(jīng)找到最低費用路徑的節(jié)點集合。

Dijkstra算法

算法描述

（1）初始化（1#～6#）
N’ ={源節(jié)點u}；

• 對所有不在N‘ 中的節(jié)點v，標出其D(v)值：
• 節(jié)點v與源節(jié)點u直接相連，D(v) = c(u，v)
• 節(jié)點v與源節(jié)點u不直接相連 ，D(v) = ∞

（2）找出一個到源節(jié)點的費用最低的節(jié)點w，并以此更新其它點D(v) 值

• 從不在N’ 中的節(jié)點中找出一個D(w)值最小的節(jié)點w，并將w加入到N’ 中。(9#～#10)
• 對不在N‘ 中，但與節(jié)點w是鄰居的節(jié)點v，用新的值更新
  D(v)=min[D(v)，D(w)+c(w,v)]
  將節(jié)點v原值與節(jié)點v現(xiàn)經(jīng)節(jié)點w到源節(jié)點的值比較，取小

（3）重復步驟(2)
直到所有的網(wǎng)絡(luò)節(jié)點都在N’ 中為止。

• 對于每個節(jié)點，都得到從源節(jié)點沿著它的最低費用路徑的前驅(qū)節(jié)點；
• 每個前驅(qū)節(jié)點，又可得到它的前驅(qū)節(jié)點；以此繼續(xù)，可以得到到所有目的節(jié)點的完整路徑。
  如節(jié)點z的前驅(qū)節(jié)點依次為： z->y->x->u
• 得出從源節(jié)點u到節(jié)點z的最低費用路徑為：uxyz，費用為4。

• 構(gòu)建最低費用路徑樹
  • 根據(jù)目的節(jié)點找出順序和其費用以及前驅(qū)節(jié)點，可以畫出源節(jié)點u到所有目的節(jié)點的最低費用路徑樹。
  • 根據(jù)得到的所有目的節(jié)點的完整路徑，或最低費用路徑樹，可以生成源節(jié)點的轉(zhuǎn)發(fā)表。

轉(zhuǎn)發(fā)表：存放從源節(jié)點到每個目的節(jié)點的最低費用路徑上的下一跳節(jié)點。即指出對于發(fā)往某個目的節(jié)點的分組，從該節(jié)點發(fā)出后的下一個節(jié)點。

構(gòu)建轉(zhuǎn)發(fā)表

默認路由 * ：表示所有具有相同“下一跳”的表項。即將“下一跳”相同的項合并為一項，目的節(jié)點用“*”表示。優(yōu)先級最低，轉(zhuǎn)發(fā)分組時，當找不到對應表項時，才使用默認路由。

Dijkstra算法：討論

計算復雜度

• 設(shè)n個節(jié)點(除源節(jié)點)，最壞情況下要經(jīng)多少次計算才能找到從源節(jié)點到所有目的節(jié)點的最低費用路徑?
  • 第一次迭代：搜索所有的n個節(jié)點以確定最低費用節(jié)點
  • 第二次迭代：檢查n-1個節(jié)點；
  • 第三次：檢查n-2個節(jié)點；
    依次類推。
    所有迭代中需要搜尋的節(jié)點總數(shù)為n(n+1)/2。
• 算法復雜性為n平方階序O(n2)。
• 更有效的執(zhí)行可能: O(nlogn)

可能產(chǎn)生振蕩

4.5.2 距離向量路由算法(Distance Vector)

• 距離向量路由算法是一種迭代的、異步的和分布式的算法。
  • 分布式：每個節(jié)點都從其直接相連鄰居接收信息，進行計算，再將計算結(jié)果分發(fā)給鄰居。
  • 迭代：計算過程一直持續(xù)到鄰居之間無更多信息交換為止。
  • 異步：不要求所有節(jié)點相互之間步伐一致地操作。
  • 自我終結(jié)：算法能自行停止。

每個節(jié)點和鄰居交換距離矢量，測量到鄰居的代價，可以算出經(jīng)過鄰居到每一個目標的代價值

最低費用表示

Bellman-Ford方程:

dx(y) = minv{c(x,v)+ dv(y)}
dx(y)：節(jié)點x到節(jié)點y的最低費用路徑的費用。
v: 節(jié)點x的鄰居節(jié)點。
c(x,v)+ dv(y)：x與某個鄰居v之間的直接鏈路費用c(x,v)加上鄰居v到y(tǒng)的最小費用。即x經(jīng)v到節(jié)點y的最小的路徑費用。
minv ：從所有經(jīng)直接相連鄰居節(jié)點到節(jié)點y的費用中選取的最小路徑費用。

B-F方程舉例

得到節(jié)點u的轉(zhuǎn)發(fā)表中到目的節(jié)點z的下一跳是節(jié)點x

距離向量DV路由算法

對每個節(jié)點x
（1）初始化：
（2）更新自己的距離向量
（3）重復執(zhí)行（2），直到?jīng)]有更新的距離向量發(fā)出

異步、迭代：

本地迭代的觸發(fā)條件

• 本地鏈路代價的變化
• 從鄰居來的DV的更新信息

DV的無窮計算問題

采用水平分裂方式解決

B是A的下一跳，所以C對B報告A的距離為INF

C是B的下一跳，所以D對C報告通向A的距離為INF

節(jié)點的距離向量表

• 節(jié)點x選路表（距離表）:
• 行：該節(jié)點的距離向量Dx和其鄰居的距離向量Dv
• 列：所有目的節(jié)點。
• 節(jié)點x的距離向量Dx ，即節(jié)點x到每個目的節(jié)點y的估計費用； Dx = [Dx(y)：y在N中]
• 節(jié)點x每個鄰居的距離向量Dv ，即x的鄰居v到每個目的節(jié)點y的估計費用，Dv = [Dv(y)：y在N中]

更新其距離向量

每個節(jié)點不斷向鄰居發(fā)送其距離向量拷貝；
當節(jié)點x收到一個鄰居v的新距離向量，先保存，并用B-F公式更新自己的距離向量：
Dx(y) = minv{c(x,v)+ Dv(y)}
從所有經(jīng)鄰居v到節(jié)點y的費用中選取最小路徑費用

• 若距離向量發(fā)生改變，將新的距離向量通知給鄰居。
• 當距離向量不再變化，算法終止，此時Dx(y)收斂到dx(y)，即得到節(jié)點x到節(jié)點y的最低費用路徑。

橫軸是時間，縱軸是各個節(jié)點

• 多次重復從鄰居接收更新距離向量、重新計算選路表項、并向鄰發(fā)送更新通知的過程，一直持續(xù)到?jīng)]有更新報文發(fā)出為止。
• 算法進入靜止狀態(tài)，直到某個鏈路費用發(fā)生改變?yōu)橹埂?/li>

鏈路費用改變與鏈路故障

當一個節(jié)點檢測到從它到鄰居的鏈路費用發(fā)生變化時，就更新其距離向量，如果最低費用路徑的費用發(fā)生變化，通知其鄰居。
（1）某鏈路費用減少時情況
如圖所示，當y 到x的鏈路費用從4變?yōu)?的情況。

考慮y與z到目的節(jié)點x的距離表變化

t0：y 檢測到x的鏈路費用從4變?yōu)?，更新其距離向量，并通知其鄰居z；
t1：z收到來自y的更新報文，并更新自己的距離表，此時到節(jié)點x的最低費用減為2，并通知其鄰居y；
t2：y收到來自z的更新報文，并更新自己的距離表，此時到節(jié)點x的最低費用不變?nèi)詾?。不發(fā)送更新報文，算法靜止。
當x與y之間費用減少，DV算法只需兩次迭代到達靜止狀態(tài)。

節(jié)點之間鏈路費用減少的“好消息”在網(wǎng)絡(luò)中能迅速傳播。

（2）某鏈路費用增加時情況
如圖所示，假設(shè)x與y之間的鏈路費用從4增加到60。

• 鏈路費用變化前
  Dy(x)=4 ，Dy(z)=1， Dz(y)=1，Dz(x)=5

• t0 時刻：y檢測到鏈路費用從4變?yōu)?0。更新到x的最低路徑費用
  Dy(x )=min{ c(y,x)+ Dx(x), c(y,z)+ Dz(x)}
  =min{60+0,1+5}=6
  經(jīng)節(jié)點z到x費用最低，此新費用錯誤，發(fā)給節(jié)點z。

需要迭代原因：y不知道z到x需要經(jīng)過自身

• t1時刻：z收到新費用，更新其到x的最低路徑費用
  Dz(x )=min{ c(z,x)+ Dx(x), c(z,y)+ Dy(x)}
  =min{50+0,1+6}=7
  經(jīng)節(jié)點y到x費用最低，發(fā)給節(jié)點y。

• t2 時刻：y收到新費用，更新到x的最低路徑費用
  Dy(x )=min{ c(y,x)+ Dx(x), c(y,z)+ Dz(x)}
  =min{60+0,1+7}=8
  經(jīng)節(jié)點z到x費用最低，發(fā)給節(jié)點z。
  ……
  節(jié)點y或z的最低費用不斷更新。
• 產(chǎn)生**“選路回環(huán)”：為到達x， y通過z選路，z又通過y選路**。
  即目的地為x的分組到達y或z后，將在這兩個節(jié)點之間不停地來回反復，直到轉(zhuǎn)發(fā)表發(fā)生改變?yōu)橹埂?/li>

會不停迭代44次，直到另一條線路之和超過50

• 上述循環(huán)將持續(xù)44次迭代 (y與z之間的報文交換)，直到z最終算出它經(jīng)由y的路徑費用大于50為止。并確定：
  • z到x的最低費用路徑：zx
  • y到x的最低費用路徑：yzx
• 說明：鏈路費用增加的“壞消息”傳播很慢！
  當鏈路費用增加很大，會出現(xiàn)“計數(shù)到無窮”問題。
  如鏈路費用c(y，x)變?yōu)?0000，c(z，x)變?yōu)?999時。

毒性逆轉(zhuǎn)

計數(shù)到無窮的解決辦法：毒性逆轉(zhuǎn)
假如 Z通過 Y 到達 X ，則Z告訴Y：它到X的距離是無窮大，Y將不會再經(jīng)過Z到X

Z向Y撒了一個善意的謊言，使得只要Z經(jīng)過Y選路到X，它就會一直持續(xù)講述這個謊言，這樣Y也就永遠不會嘗試從Z選路到X了，也就避免了環(huán)路問題

• 毒性逆轉(zhuǎn)可以完全解決計數(shù)到無窮的問題嗎？
  ——不能，如果三個以上節(jié)點的環(huán)路，則不能被毒性逆轉(zhuǎn)技術(shù)檢測到。

• 其它解決環(huán)路的方法：
  • 定義最大度量(以防止計數(shù)至無窮大 )
  • 抑制計時器
  • 水平分割
  • 路由毒化
  • 觸發(fā)更新

LS算法與DV算法比較

• 消息復雜度：【DV勝出】
  • LS算法：知道網(wǎng)絡(luò)每條鏈路的費用，需發(fā)送O(nE)個報文；當一條鏈路的費用變化時，必須通知所有節(jié)點
  • DV算法：迭代時，僅在兩個直接相連鄰居之間交換報文；當鏈路費用改變時，只有該鏈路相連的節(jié)點的最低費用路徑發(fā)生改變時，才傳播已改變的鏈路費用。
• 收斂速度：【LS勝出】
  • LS算法：需要O(nE)個報文和O(n2)的搜尋，可能會振蕩
  • DV算法：收斂較慢。可能會遇到選路回環(huán)，或計數(shù)到無窮的問題。
• 健壯性：當一臺路由器發(fā)生故障、操作錯誤或受到破壞時，會發(fā)生什么情況?【LS勝出】
  • LS算法：路由器向其連接的一條鏈路廣播不正確費用，路由計算基本獨立（僅計算自己的轉(zhuǎn)發(fā)表），有一定健壯性。
  • DV算法：一個節(jié)點可向任意或所有目的節(jié)點發(fā)布其不正確的最低費用路徑，一個節(jié)點的計算值會傳遞給它的鄰居，并間接地傳遞給鄰居的鄰居。一個不正確的計算值會擴散到整個網(wǎng)絡(luò)。

4.6 層次選路

迄今為止，我們的路由研究都是理想化的：
所有路由器一樣的
網(wǎng)絡(luò)是 “平面的”
… 實際中并不是這樣的…

• 規(guī)模:具有20億個節(jié)點
• 路由表中不可能存儲所有的節(jié)點!
• 路由表的信息交換將淹沒數(shù)據(jù)鏈路!
• internet =眾多網(wǎng)絡(luò)組成的網(wǎng)絡(luò)
• 每個網(wǎng)絡(luò)管理者管理自己網(wǎng)絡(luò)的路由選擇-管理自治

層次選路

• 一個區(qū)域內(nèi)的路由器組成集合 “自治系統(tǒng)” (AS，autonomous system )
• 同一個自治系統(tǒng)的路由器運行相同的路由協(xié)議——區(qū)域內(nèi)路由協(xié)議
• 不同自治系統(tǒng)內(nèi)的路由器可以運行不同的區(qū)域內(nèi)路由協(xié)議

網(wǎng)關(guān)路由器

• 和其他自治系統(tǒng)內(nèi)的路由器直接相連的路由器
  • 運行域間路由協(xié)議，與其他網(wǎng)關(guān)路由器交互
• 同自治系統(tǒng)內(nèi)的所有其他路由器一樣也運行域內(nèi)路由協(xié)議

問題轉(zhuǎn)換為自治區(qū)域內(nèi)部和自治區(qū)域間的路由

優(yōu)點：

• 解決了規(guī)模問題
  • 內(nèi)部網(wǎng)關(guān)協(xié)議解決：AS內(nèi)部數(shù)量有限的路由器相互到達的問題, AS內(nèi)部規(guī)模可控
    • 如AS節(jié)點太多，可分割AS，使得AS內(nèi)部的節(jié)點數(shù)量有限
  • AS之間的路由的規(guī)模問題
    • 增加一個AS，對于AS之間的路由從總體上來說，只是增加了一個節(jié)點=子網(wǎng)（每個AS可以用一個點來表示）
    • 對于其他AS來說只是增加了一個表項，就是這個新增的AS如何走的問題
    • 擴展性強：規(guī)模增大，性能不會減得太多
• 解決了管理問題
  • 各個AS可以運行不同的內(nèi)部網(wǎng)關(guān)協(xié)議
  • 可以使自己網(wǎng)絡(luò)的細節(jié)不向外透露

域（自治系統(tǒng)）內(nèi)路由選擇

• 使用域內(nèi)路由協(xié)議，也被稱作內(nèi)部網(wǎng)關(guān)協(xié)議 (IGP)
• 標準的域內(nèi)路由協(xié)議:
  • RIP: 路由信息協(xié)議
  • OSPF: 開放式最短路徑優(yōu)先
  • IGRP: 內(nèi)部網(wǎng)關(guān)路由協(xié)議 (Cisco 所有)

RIP ( Routing Information Protocol)*

• 距離向量算法
• 包含在1982年發(fā)布的BSD-UNIX 版本中。
• 距離衡量: 跳數(shù) (max = 15 hops)

• RIP 通告
• 每隔30秒,通過響應報文在鄰居間交換距離向量 (也被稱為RIP通告,advertisement)
• 或者對方請求的情況下
• 每個通告包含了多達25個AS內(nèi)的目的子網(wǎng)的列表【自治區(qū)域的小網(wǎng)】

• RIP鏈路失敗及恢復
  若180秒后沒有收到通告，則認為鄰居死機或鏈路中斷：
• 通過故障鄰居的路由失敗
• 新的公告發(fā)送給其他鄰居
• 鄰居然后再發(fā)送新的公告 (如果轉(zhuǎn)發(fā)表發(fā)生變化)
• 鏈路故障信息快速傳播到整個網(wǎng)絡(luò)
• 毒性逆轉(zhuǎn)用于防止乒乓循環(huán) (無限距離 = 16 跳)

OSPF (Open Shortest Path First)

• “open”: 開放、公用的
• 用鏈路狀態(tài)算法
  • 分發(fā)LS 分組
  • 每個節(jié)點具有拓撲圖
  • 路由計算使用 Dijkstra算法
• 每個router都廣播OSPF通告，OSPF通告里為每個鄰居路由器設(shè)一個表項（記錄每個鄰居的鏈路特征和費用）。
• 通告會散布到 整個 自治系統(tǒng) (通過洪泛法)
  • OSPF信息直接通過 IP傳輸 (不是 TCP 或 UDP）

OSPF 優(yōu)點 (RIP所沒有的)

• 安全: 所有OSPF 消息需要認證 (防止惡意入侵)
• 允許多個相同開銷的路徑 (在 RIP中只有一條路徑)
• 對于每個鏈路, 有多個消費尺度用于不同的服務(wù)類型TOS (例如在盡力轉(zhuǎn)發(fā)時衛(wèi)星鏈路代價設(shè)置為 “低” ，而對實時應用設(shè)置為高)
• 單播和多播綜合支持:
• 多播 OSPF (MOSPF) 使用和 OSPF同樣的鏈路數(shù)據(jù)庫
• 在大的區(qū)域中使用層次 OSPF

• backbone骨干網(wǎng)
• 每一個area運行相同的域內(nèi)路由協(xié)議
• 整個是大的AS
• 通過boundary router邊界路由器連接其他AS

• 兩級層次: 本地區(qū)域, 主干區(qū)域（這些區(qū)域都是在一個自治系統(tǒng)內(nèi)）
  • 只在區(qū)域內(nèi)發(fā)送鏈路狀態(tài)通告
  • 每個節(jié)點有詳細的區(qū)域拓撲; 僅知道到達其他區(qū)域內(nèi)網(wǎng)絡(luò)的方向（即到區(qū)域邊界路由器的最短路徑）
• 區(qū)域邊界路由器（同時屬于本地區(qū)域和主干區(qū)域）:“匯總”了到本區(qū)域內(nèi)部網(wǎng)絡(luò)的路徑, 并通告給其他區(qū)域邊界路由器.
• 主干路由器：限于在主干區(qū)域內(nèi)運行OSPF路由協(xié)議（本身不是區(qū)域邊界路由器）
• 邊界路由器: 連接到其他自治系統(tǒng)

Internet 域間選路

BGP

eBGP:將子網(wǎng)可達信息發(fā)送給其他相鄰的ASes

iBGP:將獲得子網(wǎng)可達信息，發(fā)送給子網(wǎng)內(nèi)布的路由器

路由器之間都是TCP連接

• BGP (Border Gateway Protocol【邊界網(wǎng)關(guān)協(xié)議】)：事實上的標準
• BGP 為每個 AS 提供了一種手段:
• 從相鄰AS獲取子網(wǎng)可達信息
• 區(qū)域邊界網(wǎng)關(guān)路由器向該AS內(nèi)部的所有路由器傳播這些可達性信息
• 基于該可達信息和AS策略，決定到達子網(wǎng)的**“好”**路由
• 允許一個子網(wǎng)向Internet的其他部分通告它的存在 “I am here”

AS互連

• 轉(zhuǎn)發(fā)表根據(jù)AS內(nèi)和AS間選路算法而配置
  • AS域內(nèi)的選路項用于目的端在域內(nèi)的選路。
  • AS域內(nèi)和AS域間的選路項用于目的端在域外的選路。

AS域間任務(wù)

• 假設(shè)AS1中的路由器接收到了目的端是AS1外的分組。路由器將把這個分組轉(zhuǎn)發(fā)到網(wǎng)關(guān)路由器，但是是哪個網(wǎng)關(guān)路由器呢？
• AS1 需要知道:
  • 通過AS2和AS3可以到達哪些目的端
  • 將這些可達信息傳播給AS1內(nèi)的所有路由器
• 這就是域間選路的任務(wù)

• 示例：在router 1d 上設(shè)置轉(zhuǎn)發(fā)表
• 假設(shè)AS1運行域間路由協(xié)議知道網(wǎng)絡(luò)X通過網(wǎng)關(guān)1c從AS3(而不是AS2)是可達的
• 通過域內(nèi)路由協(xié)議將可達信息傳播給所有域內(nèi)路由器
• Router 1d 由域內(nèi)路由信息判斷自己的接口I 在到達1c的最小開銷路徑上
• 在轉(zhuǎn)發(fā)表里添加一項 (x,I ).

• 示例：在多個自治系統(tǒng)中選擇
• 現(xiàn)在假設(shè)AS1通過域間選路協(xié)議知道子網(wǎng)x從AS3和AS2都可以到達
• 為了配置轉(zhuǎn)發(fā)表,路由器1d必須決定通過哪個網(wǎng)關(guān)將分組轉(zhuǎn)發(fā)到目的子網(wǎng)x
• 這同時也是域內(nèi)路由協(xié)議的工作
• 熱土豆選路: 把分組送到兩個路由器中最近的一個【不考慮全局開銷】

BGP會話與通告【傳輸層實現(xiàn)網(wǎng)絡(luò)層的功能】

• 路由器對（BGP對等方）通過半永久TCP連接來交換選路信息：BGP 會話
• BGP會話和物理鏈路無關(guān)（并不總是和某條物理鏈路對應）。
• 當AS2通告一個前綴給AS1,說明AS2能夠轉(zhuǎn)發(fā)目的地址前綴是這個通告前綴的所有分組。
• AS2能夠在它的通告中匯總了這些前綴。

傳播可達信息

• 在3A和1C的eBGP會話中，AS3向AS1通告一個前綴可達信息。
• 1c通過iBGP會話向AS1中的所有路由器發(fā)布這個新的前綴可達信息。
• 1b 又將這個可達信息通過1b和2a之間的eBGP會話通告給AS2。
• 當路由器得知一個新的前綴時，就在它的轉(zhuǎn)發(fā)表中為該前綴創(chuàng)建一個項。

eBGP：AS間的BGP會話

iBGP：AS內(nèi)的BGP會話

路徑屬性 和 BGP 路由

• 當通告前綴時，通告包含了BGP屬性.
• 前綴+屬性=“路由”
• 兩個重要的屬性:
• AS-PATH: 包含了前綴的通告已經(jīng)通告過的那些AS,如 AS 67 AS 17
• NEXT-HOP: 指出到達下一個AS的具體AS間邊界路由器（可能存在多條從當前AS到達下一個AS的鏈路）
• 當網(wǎng)關(guān)路由器接收到路由通告時，使用輸入策略來決定接收/舍棄該通告。

• 按照策略進行選擇

BGP 路由選擇

• 路由器可能知道到相同前綴的多條路由，路由器必須從中選擇
• 排除規(guī)則（應用排除規(guī)則直到有一條留下）
  • 本地偏好值屬性: 具有最高偏好值的路由被選擇
  • 最短AS-PATH的路由
  • 最靠近 NEXT-HOP路由器的路由 : 熱土豆路由
  • 其他標準

BGP 報文

• BGP 報文交換使用 TCP
• BGP 報文:
  • OPEN:建立到對方的TCP連接，并對發(fā)送者進行認證
  • UPDATE:通告新路徑 (或者撤銷舊路徑)
  • KEEPALIVE:在沒有UPDATES時保持連結(jié)活躍; 也對OPEN請求作出應答
  • NOTIFICATION:報告前面報文的錯誤; 也用于關(guān)閉連結(jié)

BGP 選路策略’

• A,B,C 是提供商的網(wǎng)絡(luò)

• X,W,Y是提供商的客戶

• X是雙重的: 連接到兩個網(wǎng)絡(luò)

• X 不希望 B 通過 X 到 C的路由BXC

• … 所以 X 不會向B公告到C的路由XC

• A 向B通告路徑 AW

• B 向X通告路由BAW

• B 應該向C通告路由BAW?

  • 決不! B 路由 CBAW 沒有什么“好處”，因為 W 和 C 都不是 B的客戶
  • B 希望強迫 C通過A路由到W–CAW
  • B 只想路由它的客戶!

為什么AS內(nèi)選路和AS間選路采用不同的協(xié)議 ?

• 策略:
  • AS間: 管理員想控制本AS內(nèi)產(chǎn)生的通信流怎樣選路，以及什么信流穿過自己的網(wǎng)絡(luò)
  • AS內(nèi):單個管理者, 因此不需要策略
• 規(guī)模:
  • 層次路由節(jié)省了轉(zhuǎn)發(fā)表的大小空間，減少了路由更新的流量
• 性能:
  • AS內(nèi): 集中在性能上
  • AS間: 策略可能比性能更加重要

4.7 SDN*略

傳統(tǒng)方式

網(wǎng)絡(luò)設(shè)備難以管理，固化

網(wǎng)絡(luò)管理更容易

可編程

SDN的特點

南向接口上報狀態(tài)，下交流表

SDN控制器

網(wǎng)絡(luò)控制應用

實現(xiàn)各種各樣網(wǎng)絡(luò)功能

什么是SDN

• 軟件定義網(wǎng)絡(luò)（SDN，SoftwareDefinedNetwork）源自美國斯坦福大學CLeanState研究組提出的一種新型網(wǎng)絡(luò)創(chuàng)新架構(gòu)，可通過軟件編程的形式定義和控制網(wǎng)絡(luò)，具有控制平面和轉(zhuǎn)發(fā)平面分離及開放性可編程的特點。
• SDN的核心理念是，希望應用軟件可以參與對網(wǎng)絡(luò)的控制管理，滿足上層業(yè)務(wù)需求，通過自動化業(yè)務(wù)部署，簡化網(wǎng)絡(luò)運維。
• SDN并不是一個具體的技術(shù)，它是一種網(wǎng)絡(luò)設(shè)計理念，規(guī)劃了網(wǎng)絡(luò)的各個組成部分（軟件、硬件、轉(zhuǎn)發(fā)面和控制面）及相互之間的互動關(guān)系。

SDN的發(fā)展驅(qū)動力和優(yōu)勢

• 發(fā)展驅(qū)動力
  • 計算虛擬化驅(qū)動：靜態(tài)到動態(tài)的網(wǎng)絡(luò)變化
  • 云計算對資源的垂直整合：獨立演進到協(xié)同
  • 云計算時代IT業(yè)務(wù)的發(fā)展
  • 數(shù)據(jù)中心資源：需要隨業(yè)務(wù)跨地域整合，并使數(shù)據(jù)中心間廣域流量增大
• 優(yōu)勢
  • 統(tǒng)一便捷的管理
    • 解決網(wǎng)絡(luò)中設(shè)備越來越多樣化問題
  • 無縫的版本升級
    • 解決設(shè)備版本升級對業(yè)務(wù)的影響
  • 網(wǎng)絡(luò)數(shù)據(jù)可視化
  • 整體的流量調(diào)度
  • ……

SDN的相關(guān)組織

• ONF（open network foundation ）：openflow
  該組織的發(fā)起者為google、facebook 、微軟等由客戶驅(qū)動的組織，負責推動SDN網(wǎng)絡(luò)的部署
• IETF I2RS interface to route system
  I2RS實現(xiàn)路由系統(tǒng)的開放訪問接口標準化，通過外部控制平面對設(shè)備控制平面進行擴展，也不是完全取代現(xiàn)有控制平面，可以實現(xiàn)基于控制層面的hybrid SDN
• 國際主流運營商發(fā)起成立的ETSI： 網(wǎng)絡(luò)功能虛擬化工作組（Network Function Virtualizetion，NFV）
  NFV的目標是利用當前的一些IT虛擬化技術(shù)，講多種網(wǎng)絡(luò)設(shè)備虛擬到大量符合行業(yè)標準的物理服務(wù)器、交換機或者存儲設(shè)備上，然后在這些標準的硬件上運行各種執(zhí)行這些網(wǎng)絡(luò)功能（路由、安全功能、負載均衡、SBC等）
• Opendaylight
  由各軟硬件廠商成立目標打造一個開源的基于SDN的平臺框架

SDN技術(shù)的應用方向

• 數(shù)據(jù)中心
  • 虛擬機聯(lián)動/多租戶
  • 流量監(jiān)視/擁塞發(fā)現(xiàn)/自動分流
  • 可編程/自定義路由
  • 自動化管理與運維
• 廣域網(wǎng)
  • 流量工程(TE)
  • 流量識別與差異化調(diào)度
  • 業(yè)務(wù)QoS自動部署與保證
• 無線、安全等
  • 業(yè)務(wù)動態(tài)隔離及權(quán)限控制
  • 統(tǒng)一安全防護
  • BYOD
  • AC云

SDN：通用轉(zhuǎn)發(fā)

• SDN的核心思想是建立一個通用轉(zhuǎn)發(fā)體系

? ——每個交換設(shè)備包含一個流表(flow table). 流表由一個邏輯上中心化的控制器（遠程控制器）來計算和分發(fā)

SDN體系結(jié)構(gòu)及特征

特 征

• 基于流的轉(zhuǎn)發(fā)
• 數(shù)據(jù)平面與控制平面分離
• 網(wǎng)絡(luò)控制功能：位于數(shù)據(jù)平面交換機外部
• 可編程的網(wǎng)絡(luò)

SDN控制器的組件

網(wǎng)絡(luò)層:總結(jié)

• 我們已經(jīng)學習了:
  • 網(wǎng)絡(luò)層服務(wù)
  • 路由原理: 鏈路狀態(tài)和距離矢量
  • 層次路由
  • IP
  • Internet 選擇協(xié)議 RIP, OSPF, BGP
  • 路由器的內(nèi)部結(jié)構(gòu)
  • IPv6

網(wǎng)絡(luò)層提供的服務(wù)和功能
主機通信
虛電路和數(shù)據(jù)報
轉(zhuǎn)發(fā)
選路
路由器工作原理
網(wǎng)際協(xié)議IP
IP報文、IP分片和重組
IP編址和IP子網(wǎng)
IP地址分類和無分類編址CIDR
NAT網(wǎng)絡(luò)地址轉(zhuǎn)換
IPv6協(xié)議及特點、IPv4和IPv6互通文章來源地址http://www.zghlxwxcb.cn/news/detail-486786.html

到了這里，關(guān)于【計算機網(wǎng)絡(luò)自頂向下】如何學好計網(wǎng)-第四章網(wǎng)絡(luò)層的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！