4.1網(wǎng)絡(luò)層服務(wù)

v ■從發(fā)送主機向接收主機傳送數(shù)據(jù)段（segment）

v ■發(fā)送主機：將數(shù)據(jù)段封裝到數(shù)據(jù)報（datagram）中

v ■接收主機：向傳輸層交付數(shù)據(jù)段（segment）

v ■每個主機和路由器都運行網(wǎng)絡(luò)層協(xié)議

v ■路由器檢驗所有穿越它的IP數(shù)據(jù)報的頭部域

§ 決策如何處理IP數(shù)據(jù)報

網(wǎng)絡(luò)層核心功能-轉(zhuǎn)發(fā)與路由

路由器必須維護一個轉(zhuǎn)發(fā)表

v ■轉(zhuǎn)發(fā)(forwarding):將分組從路由器的輸入端口轉(zhuǎn)移到合適的輸出端口

v ■路由(routing):確定分組從源到目的經(jīng)過的路徑

§ 路由算法（routingalgorithms）

網(wǎng)絡(luò)層核心功能-連接建立

v■某些網(wǎng)絡(luò)的重要功能:

§ATM,幀中繼, X.25

v ■數(shù)據(jù)分組傳輸之前兩端主機需要首先建立虛擬/邏輯連接

§ 網(wǎng)絡(luò)設(shè)備（如路由器）參與連接的建立（網(wǎng)絡(luò)層每一個設(shè)備都要參與連接）

v ■網(wǎng)絡(luò)層連接與傳輸層連接的對比:

§ 網(wǎng)絡(luò)層連接:兩個主機之間(路徑上的路由器等網(wǎng)絡(luò)設(shè)備參與其中)

§ 傳輸層連接:兩個應(yīng)用進(jìn)程之間（對中間網(wǎng)絡(luò)設(shè)備透明）

網(wǎng)絡(luò)層服務(wù)模型

v■無連接服務(wù)(connection-less service):

§ 不事先為系列分組的傳輸確定傳輸路徑

§ 每個分組獨立確定傳輸路徑

§ 不同分組可能傳輸路徑不同

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

v■連接服務(wù)(connection service):

§ 首先為系列分組的傳輸確定從源到目的經(jīng)過的路徑(建立連接)

§ 然后沿該路徑（連接）傳輸系列分組

§ 系列分組傳輸路徑相同

§ 傳輸結(jié)束后拆除連接

§ 虛電路網(wǎng)絡(luò)(virtual-circuit network )

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

4.2.1虛電路網(wǎng)絡(luò)

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

v■數(shù)據(jù)報(datagram)網(wǎng)絡(luò)與虛電路(virtual-circuit)網(wǎng)絡(luò)是典型兩類分組交換網(wǎng)絡(luò)

v■數(shù)據(jù)報網(wǎng)絡(luò)提供網(wǎng)絡(luò)層無連接服務(wù)

v■虛電路網(wǎng)絡(luò)提供網(wǎng)絡(luò)層連接服務(wù)

v■類似于傳輸層的無連接服務(wù)（UDP）和面向連接服務(wù)（TCP）赘阀，但是網(wǎng)絡(luò)層服務(wù)：（傳輸層是進(jìn)程與進(jìn)程之間的連接服務(wù)戚宦，而網(wǎng)絡(luò)層是主機到主機之間的服務(wù)）

§ 主機到主機服務(wù)

§ 網(wǎng)絡(luò)核心實現(xiàn)

虛電路(Virtual circuits)

■虛電路：一條從源主機到目的主機， 類似于電路的路徑(邏輯連接)

§ 分組交換

§ 每個分組的傳輸利用鏈路的全部帶寬

§ 源到目的路徑經(jīng)過的網(wǎng)絡(luò)層設(shè)備共同完成虛電路功能

v ■通信過程：

§ 呼叫建立(call setup)→數(shù)據(jù)傳輸→拆除呼叫

v ■每個分組攜帶虛電路標(biāo)識(VC ID)， 而不是目的主機地址

v ■虛電路經(jīng)過的每個網(wǎng)絡(luò)設(shè)備（如路由器） ， 維護每條經(jīng)過它的虛電路連接狀態(tài)

v ■鏈路、 網(wǎng)絡(luò)設(shè)備資源(如帶寬蝇棉、 緩存等)可以面向VC進(jìn)行預(yù)分配

§ 預(yù)分配資源=可預(yù)期服務(wù)性能

§ 如ATM的電路仿真（CBR）

VC的具體實現(xiàn)

■每條虛電路包括:

1.從源主機到目的主機的一條路徑

2.虛電路號（VCID） ， 沿路每段鏈路一個編號

3.沿路每個網(wǎng)絡(luò)層設(shè)備（如路由器）芥永， 利用轉(zhuǎn)發(fā)表記錄經(jīng)過的每條虛電路

v ■沿某條虛電路傳輸?shù)姆纸M篡殷，攜帶對應(yīng)虛電路的VCID，而不是目的地址

v ■同一條VC埋涧，在每段鏈路上的VCID通常不同

§ 路由器轉(zhuǎn)發(fā)分組時依據(jù)轉(zhuǎn)發(fā)表改寫/替換虛電路號

VC轉(zhuǎn)發(fā)表

虛電路信令協(xié)議(signaling protocols)

v■用于VC的建立板辽、維護與拆除

§ 路徑選擇

v■應(yīng)用于虛電路網(wǎng)絡(luò)

§ 如ATM、幀中繼(frame-relay)網(wǎng)絡(luò)等

v■目前的Internet不采用

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

v ■網(wǎng)絡(luò)層無連接

v ■每個分組攜帶目的地址

v ■路由器根據(jù)分組的目的地址轉(zhuǎn)發(fā)分組

§ 基于路由協(xié)議/算法構(gòu)建轉(zhuǎn)發(fā)表

§ 檢索轉(zhuǎn)發(fā)表

§ 每個分組獨立選路

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

最長前綴匹配優(yōu)先

在檢索轉(zhuǎn)發(fā)表時棘催，優(yōu)先選擇與分組目的地址匹配前綴最長的入口（entry）劲弦。

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

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

v ■計算機之間的數(shù)據(jù)交換

§ “彈性” 服務(wù)，沒有嚴(yán)格時間需求

v ■鏈路類型眾多

§ 特點醇坝、性能各異

§ 統(tǒng)一服務(wù)困難

v ■“智能” 端系統(tǒng)(計算機)

§ 可以自適應(yīng)邑跪、性能控制、差錯恢復(fù)

v■簡化網(wǎng)絡(luò)，

復(fù)雜“邊緣”

ATM (VC網(wǎng)絡(luò))

v ■電話網(wǎng)絡(luò)演化而來

v ■核心業(yè)務(wù)是實時對話：

§ 嚴(yán)格的時間画畅、可靠性需求

§ 需要有保障的服務(wù)

v ■“啞(dumb)” 端系統(tǒng)（非智能）

§ 電話機

§ 傳真機

v■簡化“邊緣” 贸毕，

復(fù)雜網(wǎng)絡(luò)

4.3IPv4協(xié)議

4.3.1IP數(shù)據(jù)報

Internet網(wǎng)絡(luò)層

IP數(shù)據(jù)報(分組)格式

v ■版本號字段占4位：IP協(xié)議的版本號

§E.g. 4→IPv4，6→IPv6

v ■首部長度字段占4位：IP分組首部長度

§ 以4字節(jié)為單位

§E.g. 5→IP首部長度為20(5×4)字節(jié)

v ■服務(wù)類型(TOS)字段占8位：指示期望獲得哪種類型的服務(wù)

§1998年這個字段改名為區(qū)分服務(wù)

§ 只有在網(wǎng)絡(luò)提供區(qū)分服務(wù)(DiffServ)時使用

§ 一般情況下不使用夜赵，通常IP分組的該字段(第2字節(jié))的值為00H

v ■總長度字段占16位：IP分組的總字節(jié)數(shù)(首部+數(shù)據(jù))

§ 最大IP分組的總長度：65535B

§ 最小的IP分組首部：20B

§IP分組可以封裝的最大數(shù)據(jù)：65535-20=65515B

v ■生存時間（TTL） 字段占8位：IP分組在網(wǎng)絡(luò)中可以通過的路由器數(shù)（或跳步數(shù)）

§ 路由器轉(zhuǎn)發(fā)一次分組，TTL減1

§ 如果TTL=0乡革，路由器則丟棄該IP分組

v ■協(xié)議字段占8位： 指示IP分組封裝的是哪個協(xié)議的數(shù)據(jù)包

§ 實現(xiàn)復(fù)用/分解

§E.g. 6為TCP寇僧，表示封裝的為TCP段；17為UDP沸版， 表示封裝的是UDP數(shù)據(jù)報

■首部校驗和字段占16位：實現(xiàn)對IP分組首部的差錯檢測

§ 計算校驗和時嘁傀，該字段置全0

§ 采用反碼算數(shù)運算求和，和的反碼作為首部校驗和字段

§ 逐跳計算视粮、逐跳校驗

路由器轉(zhuǎn)發(fā)的時候因為TTL的更改每次轉(zhuǎn)發(fā)都要重新校驗和計算校驗和

■源IP地址细办、目的IP地址字段各占32位：分別標(biāo)識發(fā)送分組

的源主機/路由器(網(wǎng)絡(luò)接口)和接收分組的目的主機/路由器

（網(wǎng)絡(luò)接口）的IP地址

■選項字段占長度可變，范圍在1~40B之間：攜帶安全蕾殴、源選路徑（發(fā)送數(shù)據(jù)報的時候就把源主機和目的主機的路徑以及確定下來）笑撞、時間戳和路由記錄等內(nèi)容

§ 實際上很少被使用（主要用于網(wǎng)絡(luò)探測和度量)

v ■填充字段占長度可變，范圍在0~3B之間：目的是補齊整個首部钓觉，符合32位對齊茴肥，即保證首部長度是4字節(jié)的倍數(shù)

4.3.2IP分片

最大傳輸單元(MTU)

v 網(wǎng)絡(luò)鏈路存在MTU (最大傳輸單元)—鏈路層數(shù)據(jù)幀可封裝數(shù)據(jù)的上限

§ 不同鏈路的MTU不同

IP分片與重組

v ■大IP分組向較小MTU鏈路轉(zhuǎn)發(fā)時， 可以被“分片”(fragmented)（也可以不分荡灾，不允許路由分片就把該MTU扔掉）

§1個IP分組分為多片IP分組

§IP分片到達(dá)目的主機后進(jìn)行“重組”(reassembled)

v■IP首部的相關(guān)字段用于標(biāo)識分片以及確定分片的相對順序

§ 總長度瓤狐、標(biāo)識、標(biāo)志位和片偏移

IP分組格式

v ■標(biāo)識字段占16位：標(biāo)識一個IP分組

§IP協(xié)議利用一個計數(shù)器批幌，每產(chǎn)生IP分組計數(shù)器加1础锐，作為該IP分組的標(biāo)識（標(biāo)識位加1）

v ■標(biāo)志位字段占3位：

§DF (Don't Fragment)

§MF (More Fragment)

§DF =1：禁止分片；

DF =0：允許分片

§MF =1：非最后一片荧缘；

MF =0：最后一片(或未分片)

v ■片偏移字段占13位：一個IP分組分片封裝原IP分組數(shù)據(jù)的相對偏移量

§ 片偏移字段以8字節(jié)為單位

IP分片過程

v ■假設(shè)原IP分組總長度為L皆警，待轉(zhuǎn)發(fā)鏈路的MTU為M

v ■若L>M，且DF=0截粗，則可以/需要分片

v ■分片時每個分片的標(biāo)識復(fù)制原IP分組的標(biāo)識

v ■通常分片時耀怜，除最后一個分片，其他分片均分為MTU允許的最大分片

v ■一個最大分片可封裝的數(shù)據(jù)應(yīng)該是8的倍數(shù)桐愉， 因此财破， 一個最大分片可封裝的數(shù)據(jù)為：

v■需要的總片數(shù)為：

v ■每片的片偏移字段取值為：

v ■每片的總長度字段為：

v ■每片的MF標(biāo)志位為：

4.3.3IP編址(addressing)

v ■IP分組：

§ 源地址(SA)-從哪兒來

§ 目的地址(DA)-到哪兒去

v ■接口(interface):主機/路由器與物理鏈路的連接

§ 實現(xiàn)網(wǎng)絡(luò)層功能

§ 路由器通常有多個接口

§ 主機通常只有一個或兩個接口(e.g.，有線的以太網(wǎng)接口从诲，無線的802.11接口)

v■IP地址: 32比特(IPv4)編號標(biāo)識主機左痢、路由器的接口

v ■IP地址與每個接口關(guān)聯(lián)

IP子網(wǎng)（Subnets）

v■IP地址:

§ 網(wǎng)絡(luò)號(NetID)– 高位比特

§ 主機號(HostID)– 低位比特

v■IP子網(wǎng)：

§IP地址具有相同網(wǎng)絡(luò)號的設(shè)備接口

§ 不跨越路由器（第三及以上層網(wǎng)絡(luò)設(shè)備）可以彼此物理聯(lián)通的接口

4.3.4有類IP地址

特殊IP地址

私有（Private）IP地址

4.3.5IP子網(wǎng)劃分與子網(wǎng)掩碼

子網(wǎng)劃分

■區(qū)別一個IP子網(wǎng)更小范圍網(wǎng)絡(luò)（子網(wǎng)）

v■IP地址:

§ 網(wǎng)絡(luò)號(NetID)– 高位比特

§ 子網(wǎng)號(SubID)– 原網(wǎng)絡(luò)主機號部分比特

§ 主機號(HostID)– 低位比特

子網(wǎng)掩碼

v■形如IP地址:

§32位

§ 點分十進(jìn)制形式

v ■取值：

§NetID、SubID位全取1

§HostID位全取0

v■例如：

§A網(wǎng)的默認(rèn)子網(wǎng)掩碼為：255.0.0.0

§B網(wǎng)的默認(rèn)子網(wǎng)掩碼為：255.255.0.0

§C網(wǎng)的默認(rèn)子網(wǎng)掩碼為：255.255.255.0

§ 借用3比特劃分子網(wǎng)的B網(wǎng)的子網(wǎng)掩碼為：255.255.224.0

子網(wǎng)掩碼的應(yīng)用

v將IP分組的目的IP地址與子網(wǎng)掩碼按位與運算，提取子網(wǎng)地址

4.3.6CIDR與路由聚合

CIDR

無類域間路由(CIDR: Classless InterDomain Routing)

§ ■消除傳統(tǒng)的A類俊性、B類和C類地址界限

§NetID+SubID→Network Prefix (Prefix)可以任意長度

§ ■融合子網(wǎng)地址與子網(wǎng)掩碼略步，方便子網(wǎng)劃分

§ 無類地址格式：a.b.c.d/x，其中x為前綴長度

CIDR與路由聚合

無類域間路由(CIDR: Classless InterDomain Routing)

§ ■提高IPv4地址空間分配效率

§ ■提高路由效率

§ 將多個子網(wǎng)聚合為一個較大的子網(wǎng)

§ 構(gòu)造超網(wǎng)（supernetting）

§ 路由聚合（route aggregation）

路由聚合

使用單個網(wǎng)絡(luò)前綴通告多個網(wǎng)絡(luò)的方式稱為路由聚合

層級編址使得路由信息通告更高效:

選用更具體的路由：最長前綴匹配優(yōu)先定页！

4.4DHCP協(xié)議

如何獲得IP地址?

v ■“硬編碼”

§ 靜態(tài)配置

v ■動態(tài)主機配置協(xié)議-DHCP: Dynamic Host Configuration Protocol

§ ? 從服務(wù)器動態(tài)獲忍吮　：

IP地址

子網(wǎng)掩碼

默認(rèn)網(wǎng)關(guān)地址（即第一跳路由器的地址：當(dāng)這個子網(wǎng)內(nèi)IP報要離開子網(wǎng)的時候應(yīng)該向哪個網(wǎng)絡(luò)轉(zhuǎn)發(fā)）

DNS服務(wù)器名稱與IP地址

§ ? “即插即用”

§ ? 允許地址重用（用完某一個ip地址，用完可以還回去給別的主機用）

§ ? 支持在用地址續(xù)租

§ ? 支持移動用戶加入網(wǎng)絡(luò)

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

v ■主機廣播 “DHCP discover”(發(fā)現(xiàn)報文)

v ■DHCP服務(wù)器利用 “DHCP offer”(提供報文)進(jìn)行響應(yīng)（可以提供DHCP服務(wù)）

v ■主機請求IP地址:“DHCP request”(請求報文)

v ■DHCP服務(wù)器分配IP地址:“DHCP ack”(確認(rèn)報文)

DHCP工作過程示例

vDHCP協(xié)議在應(yīng)用層實現(xiàn)

§ 請求報文封裝到UDP數(shù)據(jù)報中

§IP廣播（映射為鏈路層廣播）

§ 鏈路層廣播(e.g.以太網(wǎng)廣播）

■DHCP服務(wù)器構(gòu)造ACK報文

§ 包括分配給客戶的IP地址典徊、子網(wǎng)掩碼杭煎、默認(rèn)網(wǎng)關(guān)、DNS服務(wù)器地址

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

動機:

§ ■只需/能從ISP申請一個IP地址

?IPv4地址耗盡

§ ■本地網(wǎng)絡(luò)設(shè)備IP地址的變更卒落，無需通告外界網(wǎng)絡(luò)

§ ■變更ISP時羡铲，無需修改內(nèi)部網(wǎng)絡(luò)設(shè)備IP地址

§ ■內(nèi)部網(wǎng)絡(luò)設(shè)備對外界網(wǎng)絡(luò)不可見，即不可直接尋址(安全)

實現(xiàn):

§ ■替換

? 利用(NAT IP地址,新端口號)替換每個外出IP數(shù)據(jù)報的(源IP地址,源端口號)

§ ■記錄

? 將每對(NAT IP地址,新端口號)與(源IP地址,源端口號)的替換信息存儲到NAT轉(zhuǎn)換表中

§ ■替換

? 根據(jù)NAT轉(zhuǎn)換表儡毕，利用(源IP地址,源端口號)替換每個進(jìn)入內(nèi)網(wǎng)IP數(shù)據(jù)報的(目的IP地址,目的端口號)也切，即(NAT IP地址,新端口號)

v■16-bit端口號字段:

§ 可以同時支持60,000多并行連接！

v■NAT主要爭議:

§ ? 路由器應(yīng)該只處理第3層功能

§ ? 違背端到端通信原則

應(yīng)用開發(fā)者必須考慮到NAT的存在腰湾，e.g., P2P應(yīng)用

§ ? 地址短缺問題應(yīng)該由IPv6來解決

NAT穿透問題

v■客戶期望連接內(nèi)網(wǎng)地址為10.0.0.1的服務(wù)器

§ 客戶不能直接利用地址10.0.0.1直接訪問服務(wù)器

§ 對外唯一可見的地址是NAT地址: 138.76.29.7

v■解決方案1:靜態(tài)配置NAT雷恃，將特定端口的連接請求轉(zhuǎn)發(fā)給服務(wù)器

§e.g., (138.76.29.7, 2500)總是轉(zhuǎn)發(fā)給(10.0.0.1, 25000)

v■解決方案2:利用UPnP(Universal Plug and Play)互聯(lián)網(wǎng)網(wǎng)關(guān)設(shè)備協(xié)議(IGDInternet Gateway Device )自動配置:v

學(xué)習(xí)到NAT公共IP地址(138.76.29.7)

v 在NAT轉(zhuǎn)換表中，增刪端口映射

■解決方案3:中繼(如Skype)

§NAT內(nèi)部的客戶與中繼服務(wù)器建立連接

§ 外部客戶也與中繼服務(wù)器建立連接

§ 中繼服務(wù)器橋接兩個連接的分組

4.6互聯(lián)網(wǎng)控制報文協(xié)議(ICMP)

v ■互聯(lián)網(wǎng)控制報文協(xié)議ICMP (Internet Control Message Protocol)支持主機或路由器：

§ 差錯(或異常)報告

§ 網(wǎng)絡(luò)探詢（發(fā)送特殊報文來實現(xiàn)）

v ■兩類ICMP報文:

§ 差錯報告報文(5種)

? 目的不可達(dá)

? 源抑制(Source Quench)（設(shè)計目的是用于擁塞控制费坊，目前路由器已滿褂萧，發(fā)送到源主機，控制發(fā)送速率葵萎，目前未使用）

? 超時/超期

? 參數(shù)問題（報文頭部某些參數(shù)有問題导犹，丟棄并發(fā)送）

? 重定向(Redirect)

§ 網(wǎng)絡(luò)探詢報文(2組)

? 回聲(Echo)請求與應(yīng)答報文(Reply)（eig：ping）

? 時間戳請求與應(yīng)答報文

例外情況

v ■幾種不發(fā)送ICMP差錯報告報文的特殊情況：

§ 對ICMP差錯報告報文不再發(fā)送ICMP差錯報告報文（如果已經(jīng)有一個ICMP差錯報文，這個報文出錯不會再次發(fā)送ICMP報文）

§ 除第1個IP數(shù)據(jù)報分片外羡忘， 對所有后續(xù)分片均不發(fā)送ICMP差錯報告報文

§ 對所有多播IP數(shù)據(jù)報均不發(fā)送ICMP差錯報告報文

§ 對具有特殊地址（如127.0.0.0或0.0.0.0） 的IP數(shù)據(jù)報不發(fā)送ICMP差錯報告報文

v ■幾種ICMP報文已不再使用

§ 信息請求與應(yīng)答報文

§ 子網(wǎng)掩碼請求和應(yīng)答報文

§ 路由器詢問和通告報文

ICMP報文的格式

vICMP報文封裝到IP數(shù)據(jù)報中傳輸

ICMP差錯報告報文數(shù)據(jù)封裝

4.7IPv6簡介

IPv6：動機

v ■最初動機: 32位IPv4地址空間已分配殆盡

v ■其他動機:改進(jìn)首部格式

§ 快速處理/轉(zhuǎn)發(fā)數(shù)據(jù)報

§ 支持QoS

■IPv6數(shù)據(jù)報格式:

§ 固定長度的40字節(jié)基本首部

§ 不允許分片

IPv6數(shù)據(jù)報格式

優(yōu)先級(priority):標(biāo)識數(shù)據(jù)報的優(yōu)先級

流標(biāo)簽(flow Label):標(biāo)識同一“流”中的數(shù)據(jù)報（根據(jù)不同流標(biāo)簽用于不同服務(wù)）

下一個首部(next header):標(biāo)識下一個選項首部或上層協(xié)議首部(如TCP首部)（指向下一個擴展首部谎痢，沒有就指向上層協(xié)議首部）

其他改變vs IPv4

v■校驗和(checksum):徹底移除，以減少每跳處理時間

v■選項(options):允許卷雕，但是從基本首部移出节猿，定義多個選項首部，通過“下一個首部”字段指示

v■ICMPv6:新版ICMP

§ 附加報文類型漫雕，e.g.“Packet Too Big”

§ 多播組管理功能（IPv4中的IGMP集成到ICMPv6上）

IPv6地址表示形式

IPv6基本地址類型

IPv4向IPv6過渡

v■不可能在某個時刻所有路由器同時被更新為IPv6

§ 不會有 “標(biāo)志性的日期”

§IPv4和IPv6路由器共存的網(wǎng)絡(luò)如何運行滨嘱？

v■隧道(tunneling): IPv6數(shù)據(jù)報作為IPv4數(shù)據(jù)報的載荷進(jìn)行封裝，穿越IPv4網(wǎng)絡(luò)

隧道（tunneling）

4.8路由算法

路由與轉(zhuǎn)發(fā)

網(wǎng)絡(luò)抽象：圖

路由算法分類

■靜態(tài)路由vs動態(tài)路由浸间？

·靜態(tài)路由：

v 手工配置

v 路由更新慢

v 優(yōu)先級高

·動態(tài)路由（基于算法）：

v 路由更新快

§ 定期更新

§ 及時響應(yīng)鏈路費用或網(wǎng)絡(luò)拓?fù)渥兓?/p>

■全局信息vs分散信息太雨？

·全局信息：

v 所有路由器掌握完整的網(wǎng)絡(luò)拓?fù)浜玩溌焚M用信息

vE.g.鏈路狀態(tài)(LS)路由算法

·分散(decentralized)信息：

v 路由器只掌握物理相連的鄰居以及鏈路費用

v 鄰居間信息交換、運算的迭代過程

vE.g.距離向量(DV)路由算法

4.8.2鏈路狀態(tài)路由算法

Dijkstra算法

v ■所有結(jié)點(路由器)掌握網(wǎng)絡(luò)拓?fù)浜玩溌焚M用

§ 通過“鏈路狀態(tài)廣播”

§ 所有結(jié)點擁有相同信息

v ■計算從一個結(jié)點(“源”)到達(dá)所有其他結(jié)點的最短路徑

§ 獲得該結(jié)點的轉(zhuǎn)發(fā)表

v ■迭代: k次迭代后魁蒜，得到到達(dá)k個目的結(jié)點的最短路徑

符號:

v■c(x,y):結(jié)點x到結(jié)點y鏈路費用囊扳；如果x和y不直接相連吩翻，則=∞

v■D(v):從源到目的v的當(dāng)前路徑費用值

v■p(v):沿從源到v的當(dāng)前路徑，v的前序結(jié)點

v■N’:已經(jīng)找到最小費用路徑的結(jié)點集合

Dijkstra算法:討論

算法復(fù)雜性:n個結(jié)點

v ■每次迭代:需要檢測所有不在集合N’中的結(jié)點w

v ■n(n+1)/2次比較: O(n2)

v ■更高效的實現(xiàn): O(nlogn)

存在震蕩(oscillations)可能:（由于不斷更新的路由狀態(tài)信息而出現(xiàn)的）

v ■e.g.,假設(shè)鏈路費用是該鏈路承載的通信量:

4.8.3距離向量路由算法

距離向量路由算法

距離向量DV:鏈路費用變化

鏈路費用變化:

v ■結(jié)點檢測本地鏈路費用變化

v ■更新路由信息锥咸，重新計算距離向量

v ■如果DV改變狭瞎，通告所有鄰居

t0 : y檢測到鏈路費用改變 ，更新DV搏予，通告其鄰居.

t1 : z收到y(tǒng)的DV更新熊锭，更新其距離向量表，計算到達(dá)x的最新最小費用雪侥，更新其DV碗殷，并發(fā)送給其所有鄰居.

t2 : y收到z的DV更新， 更新其距離向量表校镐，重新計算y的DV，未發(fā)生改變捺典，不再向z發(fā)送DV.

好消息傳播快

距離向量DV:無窮計數(shù)問題

解決辦法：

（1）毒性逆轉(zhuǎn)(poisoned reverse):

v 如果一個結(jié)點(e.g. Z)到達(dá)某目的(e.g.X)的最小費用路徑是通過某個鄰居(e.g.Y)鸟廓，則：

§ 通告給該鄰居結(jié)點到達(dá)該目的的距離為無窮大

（如果一個節(jié)點z到達(dá)某目的x的最小路徑是通過z的鄰居y實現(xiàn)，則通過z通告y它（z）去x的距離無無窮大）

（2）定義最大度量(maximum metric):

v （從一個點到另一個點）定義一個最大的有效費用值襟己，如15跳步引谜，16跳步表示∞

4.9Internet路由

4.9.1層次路由

將任意規(guī)模網(wǎng)絡(luò)抽象為一個圖計算路由-過于理想化

v 標(biāo)識所有路由器

v “扁平”網(wǎng)絡(luò)

——在實際網(wǎng)絡(luò)（尤其是大規(guī)模網(wǎng)絡(luò)）中， 不可行擎浴！

網(wǎng)絡(luò)規(guī)模：考慮6億目的結(jié)點的網(wǎng)絡(luò)

v ■路由表幾乎無法存儲员咽！

v ■路由計算過程的信息（e.g.鏈路狀態(tài)分組、DV）交換量巨大贮预，會淹沒鏈路贝室！

管理自治：

v ■每個網(wǎng)絡(luò)的管理可能都期望自主控制其網(wǎng)內(nèi)的路由

v ■互聯(lián)網(wǎng)(internet) =網(wǎng)絡(luò)之網(wǎng)絡(luò)(network of networks)

v■聚合路由器為一個區(qū)域：自治系統(tǒng)AS(autonomous systems)

v■同一AS內(nèi)的路由器運行相同的路由協(xié)議(算法)

§ 自治系統(tǒng)內(nèi)部路由協(xié)議(“intra-AS”routing protocol)

§ 不同自治系統(tǒng)內(nèi)的路由器可以運行不同的AS內(nèi)部路由協(xié)議

■網(wǎng)關(guān)路由器(gateway router):

v 位于AS“邊緣”

v 通過鏈路連接其他AS的網(wǎng)關(guān)路由器

互連的AS

自治系統(tǒng)間(Inter-AS)路由任務(wù)

v ■假設(shè)AS1內(nèi)某路由器收到一個目的地址在AS1之外的數(shù)據(jù)報:

§ 路由器應(yīng)該將該數(shù)據(jù)報轉(zhuǎn)發(fā)給哪個網(wǎng)關(guān)路由器呢？

AS1必須:

1.學(xué)習(xí)到哪些目的網(wǎng)絡(luò)可以通過AS2到達(dá)仿吞，哪些可以通過AS3到達(dá)

2.將這些網(wǎng)絡(luò)可達(dá)性信息傳播給AS1內(nèi)部路由器

4.9.2RIP協(xié)議

AS內(nèi)部路由

v■Internet采用層次路由

v■AS內(nèi)部路由協(xié)議也稱為內(nèi)部網(wǎng)絡(luò)協(xié)議IGP(interior gateway protocols)

v■最常見的AS內(nèi)部路由協(xié)議:

§ 路由信息協(xié)議：RIP(Routing Information Protocol)

§ 開放最短路徑優(yōu)先：OSPF(Open Shortest Path First)

§ 內(nèi)部網(wǎng)關(guān)路由協(xié)議：IGRP(Interior Gateway Routing Protocol)

§ ·Cisco私有協(xié)議

RIPv

■早于1982年隨BSD-UNIX操作系統(tǒng)發(fā)布

v ■距離向量路由算法

§ 距離度量：跳步數(shù)(max = 15 hops),每條鏈路1個跳步

§ 每隔30秒滑频，鄰居之間交換一次DV，成為通告(advertisement)

§ 每次通告：最多25個目的子網(wǎng)(IP地址形式)

RIP:鏈路失效唤冈、恢復(fù)

如果180秒沒有收到通告→鄰居/鏈路失效

§ ■經(jīng)過該鄰居的路由不可用

§ 重新計算路由

§ ■向鄰居發(fā)送新的通告

§ ■鄰居再依次向外發(fā)送通告（如果轉(zhuǎn)發(fā)表改變）

§ ■鏈路失效信息能否快速傳播到全網(wǎng)峡迷？

§ 可能發(fā)生無窮計數(shù)問題

§ ■毒性逆轉(zhuǎn)技術(shù)用于預(yù)防乒乓(ping-pong)環(huán)路(另外：無窮大距離= 16 hops)

RIP路由表的處理

v■RIP路由表是利用一個稱作route-d (daemon)的應(yīng)用層進(jìn)程進(jìn)行管理（根據(jù)功能劃分層次）

v應(yīng)用進(jìn)程實現(xiàn)

v■通告報文周期性地通過UDP數(shù)據(jù)報發(fā)送

4.9.3OSPF協(xié)議簡介

OSPF (Open Shortest Path First)（自治系統(tǒng)內(nèi)部協(xié)議）

■v“開放”:公眾可用

v■采用鏈路狀態(tài)路由算法

§LS分組擴散（通告）

§ 每個路由器構(gòu)造完整的網(wǎng)絡(luò)(AS)拓?fù)鋱D

§ 利用Dijkstra算法計算路由

v■OSPF通告中每個入口對應(yīng)一個鄰居

v■OSPF通告在整個AS范圍泛洪

§OSPF報文直接封裝到IP數(shù)據(jù)報中

v■與OSPF極其相似的一個路由協(xié)議:IS-IS路由協(xié)議

OSPF優(yōu)點(RIP不具備)

v■安全(security):所有OSPF報文可以被認(rèn)證(預(yù)防惡意入侵)（通過每臺路由器配置相同的口令；MD5校驗）

v■允許使用多條相同費用的路徑(RIP只能選一條)

v■對于每條鏈路你虹，可以針對不同的TOS設(shè)置多個不同的費用度量(e.g.,衛(wèi)星鏈路可以針對“盡力”(best effort) ToS設(shè)置“低”費用绘搞；針對實時ToS設(shè)置“高”費用)

v■集成單播路由與多播路由:

§ 多播OSPF協(xié)議(MOSPF)與OSPF利用相同的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)

v■OSPF支持對大規(guī)模AS分層(hierarchical)

分層的OSPF