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

1.網(wǎng)絡(luò)層的主要功能

主要功能就是：將源端數(shù)據(jù)包一路送到接收方。
無連接服務(wù)的實(shí)現(xiàn)：數(shù)據(jù)報(bào)子網(wǎng)
對(duì)于無連接服務(wù)來說每個(gè)數(shù)據(jù)包都獨(dú)立地被注入到網(wǎng)絡(luò)中，并且每個(gè)數(shù)據(jù)包獨(dú)立路由，不需要建立任何設(shè)置（X.25, ATM）

• 每個(gè)數(shù)據(jù)報(bào)攜帶目的地址

• 每個(gè)報(bào)文獨(dú)立尋徑

  
  
  image.png

面向連接服務(wù)的實(shí)現(xiàn)：虛電路子網(wǎng)
面向連接的服務(wù)，需要一個(gè)虛電路網(wǎng)絡(luò)，虛電路的目的是避免為每個(gè)數(shù)據(jù)包選擇一條新路徑，當(dāng)建立一個(gè)連接時(shí)，從源機(jī)器到目標(biāo)機(jī)器之間的一條路徑就被當(dāng)做這個(gè)連接的一部分被確定下來。（IP）

• 在連接建立的時(shí)候選路（Select a path）
• 每個(gè)分組攜帶一個(gè)連接號(hào)（connection-number）

• 當(dāng)通信完成后，連接拆除

  
  
  image.png

比較

2.理解路由算法原理

• 靜態(tài)路由選擇算法
  Dijkstra
  flooding
• 動(dòng)態(tài)路由選擇算法
  距離矢量路由（DV）：RIP
  鏈路狀態(tài)路由（LS）: OSPF
  最優(yōu)化原則：如果一個(gè)路由器 J 處在路由器I到路由器K的最優(yōu)路徑上，那么，從路由器J到路由器K的最優(yōu)路徑也在同樣的這條路徑上。

沉落樹（ sink tree ）、匯集樹：從所有的源到一個(gè)給定的目的的最優(yōu)路徑形成的一棵樹，樹根是目的結(jié)點(diǎn)。匯集樹不必是唯一的

什么時(shí)候使用靜態(tài)/動(dòng)態(tài)路由？
靜態(tài)路由：管理員手工配置的路由
適合小型的、靜態(tài)的網(wǎng)絡(luò)，開銷小

動(dòng)態(tài)路由：由路由選擇協(xié)議動(dòng)態(tài)地建立、更新和維護(hù)的路由
適合大型的、經(jīng)常變動(dòng)的網(wǎng)絡(luò)，需要維護(hù)開銷
減少了網(wǎng)絡(luò)管理員的負(fù)擔(dān)

2.1Dijkstra

2.2距離矢量路由（DV）

距離矢量路由選擇：每個(gè)路由器維護(hù)一張表，表中列出了當(dāng)前已知的到每個(gè)目標(biāo)的最佳距離，以及為了到達(dá)那個(gè)目標(biāo)，應(yīng)該從哪個(gè)目標(biāo)轉(zhuǎn)發(fā)的線路（端口）。這些表通過鄰居之間相互交換信息而不斷更新，最終每個(gè)路由器都了解到達(dá)每個(gè)目的地的最佳鏈路。

image.png

DV的工作原理

• 每個(gè)路由器（節(jié)點(diǎn)）維護(hù)兩個(gè)向量，Di和Si ，分別表示從該路由器到所有其它路由器的距離及相應(yīng)的下一跳（next hop）
• 在鄰居路由器之間交換路由信息（矢量）
• 每個(gè)路由器（節(jié)點(diǎn)）根據(jù)收到的矢量信息，更新自己的路由表

• di1：從節(jié)點(diǎn)i到節(jié)點(diǎn)1的度量（代價(jià)）
• si1 ：沿著從節(jié)點(diǎn)i到節(jié)點(diǎn)1的最優(yōu)路徑上的下一跳
• n ：網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)

當(dāng)鄰居間交換了矢量信息之后：

• 更新距離： dij= Min[dix+ dxj] ( x ∈A ) 【A—節(jié)點(diǎn)i的鄰居集合】
• 更新下一跳： Sij= x

• 例子：
  一個(gè)網(wǎng)絡(luò)拓?fù)淙缦?，某個(gè)時(shí)刻，路由器C接收到三個(gè)鄰居發(fā)過來的矢量如下：
  A B C D E F
  From router B：（5， 0， 8， 12， 6， 2）
  From router D：（16， 12， 6， 0， 9， 10）
  From router E：（7，6， 3， 9， 0， 4）
  現(xiàn)在，路由器C到 B、 D 和 E 的代價(jià)分別是 6、3 和 5，試回答路由器C更新后的路由表
  解答：
  分析：通過路由器 B、 D 和 E進(jìn)行轉(zhuǎn)發(fā)的話,路由器C的矢量分別是：
  Via router B：（ 11， 6， 14， 18， 12 ， 8）
  Via router D: （ 19， 15， 9， 3， 12， 13）
  Via router E: （ 12 ， 11， 8， 14， 5， 9）
  所以，路由器C更新后的路由表如下：
  （ 11， 6， 0， 3， 5， 8）
  （ B， B， -， D， E， B）

D-V算法的特點(diǎn)
優(yōu)點(diǎn)

• 簡單

缺點(diǎn)

• 交換的信息太大了
  路由信息傳播慢，可能導(dǎo)致路徑信息不一致
  收斂慢，度量計(jì)數(shù)到無窮
  不適合大型的網(wǎng)絡(luò)

2.2.1 RIP 路由選擇信息協(xié)議

RIP的主要特點(diǎn)

• RIP是一種典型的D-V路由選擇協(xié)議
• RIP采用了跳數(shù)（hop）作為量度（metric）
• 當(dāng)量度超過 15 跳，目的被認(rèn)為不可達(dá)
• 默認(rèn)地，每30秒鐘交換一次矢量/向量信息（全部路由表）

RIP的主要缺陷

• 不能到達(dá)量度超過15跳的目標(biāo)網(wǎng)絡(luò)
• RIP的度量（代價(jià)）是跳數(shù)，即沿途經(jīng)過的路由器的個(gè)數(shù)，有時(shí)候，并不合理，不能真正反映網(wǎng)絡(luò)的狀況
• 實(shí)際運(yùn)行中，會(huì)遇到度量計(jì)數(shù)到無窮、收斂慢等問題

DV路由可能遇到的問題
問題表現(xiàn)

• 路由環(huán)路（routing loop）
• 計(jì)數(shù)到無窮問題（Count toinfinite）
• 收斂慢的問題（slowConvergence）
  原因
• 相信錯(cuò)誤的路由信息導(dǎo)致
  解決方法：
• 定義路徑度量（代價(jià)）的最大值
• 提高收斂速度：
  水平分割
  毒性逆轉(zhuǎn)
  抑制定時(shí)器
  觸發(fā)更新

image.png

image.png

image.png

image.png

2.3 鏈路狀態(tài)路由算法（LS）及LS的實(shí)例OSPF

image.png

鏈路狀態(tài)路由的主要思想包括如下5個(gè)部分：
1.發(fā)現(xiàn)它的鄰居節(jié)點(diǎn)們，了解它們的網(wǎng)絡(luò)地址
2.設(shè)置到它的每個(gè)鄰居的成本度量
3.構(gòu)造一個(gè)分組，包含它所了解到的所有信息
4.發(fā)送這個(gè)分組給所有其他的路由器
5.計(jì)算到每個(gè)路由器的最短路徑

LS的工作原理：
1. 發(fā)現(xiàn)鄰居節(jié)點(diǎn)
當(dāng)一個(gè)路由器啟動(dòng)的時(shí)候，在每個(gè)點(diǎn)到點(diǎn)的線路發(fā)送一個(gè)特別的HELLO分組
收到HELLO分組的路由器應(yīng)該回送一個(gè)應(yīng)答，應(yīng)答中有它自己的名字
（當(dāng)兩個(gè)或更多的路由器被一個(gè)LAN連接起來，這個(gè)LAN被看作一個(gè)節(jié)點(diǎn)）
2. 設(shè)置鏈路成本
為了決定線路的開銷，路由器發(fā)送一個(gè)特別的** ECHO 分組，另一端立刻回送一個(gè)應(yīng)答
通過測量往返時(shí)間（round-trip time）** ，發(fā)送路由器可以獲得一個(gè)合理的延遲估計(jì)值
3. 構(gòu)造鏈路狀態(tài)分組
鏈路狀態(tài)分組構(gòu)造后被發(fā)送給其他的路由器，分組中包含這些信息：

• 發(fā)送方的標(biāo)識(shí)（ID of the sender）
• 序列號(hào)（sequence number ）
• 年齡（age ）
• 鄰居列表（list of neighbors ）
• 到鄰居的成本/量度（delay to eachneighbor ）

4. 發(fā)布鏈路狀態(tài)分組
基本算法：
每個(gè)分組都包含一個(gè)序列號(hào)，序列號(hào)隨著新分組產(chǎn)生而遞增
路由器記錄下他看見的所有 (源路由器，序列號(hào))對(duì)
當(dāng)一個(gè)的新的分組到達(dá)時(shí)，路由器根據(jù)它的記錄：
如果該分組是新的，就被從除了來線路外的所有其他線路轉(zhuǎn)發(fā)出去 ( flooding，泛洪)
如果是重復(fù)分組，即被丟棄(喜新厭舊)
如果該分組的序列號(hào)比對(duì)應(yīng)的源路由器發(fā)送的到過此地的分組的最大序列號(hào)還小，則該分組被當(dāng)作過時(shí)的信息而被拒
5. 計(jì)算新的路由路徑
一旦一個(gè)路由器獲得了全部的鏈路狀態(tài)分組就可以構(gòu)造出全網(wǎng)絡(luò)圖來了（Graph）
現(xiàn)在，可以使用 最短路徑算法來計(jì)算路由器之間的最短路徑了
計(jì)算結(jié)果是一棵樹，會(huì)形成相應(yīng)的路由，安裝在路由表中，引導(dǎo)數(shù)據(jù)分組的轉(zhuǎn)發(fā)

發(fā)布鏈路狀態(tài)分組基本算法遇到的問題：

• 序列號(hào)回轉(zhuǎn)，引起新老分組識(shí)別混淆
  解決辦法：使用 32-bit 的序列號(hào)，即使每秒產(chǎn)生一個(gè)分組，也需要137年才發(fā)生號(hào)碼回轉(zhuǎn)
• 如果一臺(tái)路由器崩潰，那么他將丟失自己的序列號(hào)記錄，如果他再從0開始，新分組將被當(dāng)作舊分組被拒絕
• 如果一個(gè)序列號(hào)被破壞了，比如發(fā)送方的序列號(hào)是4，但是由于產(chǎn)生了1位錯(cuò)誤，序列號(hào)被看作65540，那么，序列號(hào)為 5 – 65540的分組都被當(dāng)作過時(shí)分組而被拒絕

解決上述的路由器崩潰和序列號(hào)損壞的方法是：每個(gè)分組的序列號(hào)之后是年齡(age) ，并且每秒鐘年齡減1
當(dāng)年齡為零 ( zero )時(shí)，來自該路由器的信息被丟棄
通常地，每隔一段時(shí)間，比如10秒鐘，一個(gè)新分組就會(huì)到來，所以，只有路由器down機(jī)才可能導(dǎo)致超時(shí)（或者，連續(xù)6個(gè)間隔因?yàn)閬G失，沒有收到新的分組）

L-S 路由算法的特點(diǎn)

• 優(yōu)點(diǎn)：
  每個(gè)路由器的認(rèn)識(shí)一致
  收斂快
  適合在大型網(wǎng)絡(luò)里使用

• 缺點(diǎn)：
  每個(gè)路由器需要較大的存儲(chǔ)空間
  計(jì)算負(fù)擔(dān)很大

2.3.1 OSPF開放的路徑優(yōu)先（Open shortest path first）

OSPF開放的路徑優(yōu)先（Open shortest path first）

• 使用圖（graph）來表述真實(shí)的網(wǎng)絡(luò)
  每個(gè)路由器/Lan都是一個(gè)節(jié)點(diǎn)
  測量代價(jià)/量度（ metric）
• 計(jì)算最短路徑

OSPF分組(packet)類型：

image.png

OSPF的運(yùn)行步驟：

image.png

OSPF狀態(tài)：

image.png

3 其他路由

3.1 無類別域間路由—CIDR

• 緩解了地址枯竭的趨勢；控制甚至縮減了路由表的開銷
• 分配IP地址的時(shí)候不再以類別來分，而是按照可變長的地址塊來分配
• 路由表必須擴(kuò)展，增加一個(gè) 32-bit 的子網(wǎng)掩碼
• 每個(gè)路由表有一個(gè)三元組 (IP address, subnet mask, outgoing line)
• 當(dāng)一個(gè)分組到來到的時(shí)候
  分組中的目標(biāo)IP地址（Destination IP）被檢查
  目標(biāo)IP和子網(wǎng)掩碼進(jìn)行與操作，獲得目標(biāo)網(wǎng)絡(luò)地址，以查找路由表.
  如果路由表中有多個(gè)表項(xiàng)匹配 (這些表項(xiàng)有不同的子網(wǎng)掩碼) ，使用子網(wǎng)掩碼最長的那個(gè)表項(xiàng)

3.2 掌握NAT/PAT基本原理

• NAT：net address translate NAT
  私有IP地址和公有IP地址之間的轉(zhuǎn)換。

• PAT：port address translate（超載）
  將多個(gè)私有IP地址影射到同一個(gè)公有IP地址的不同端口

NAT--一個(gè)IP地址耗盡的快速修補(bǔ)方案

• 內(nèi)部網(wǎng)絡(luò)使用私人地址，當(dāng)內(nèi)網(wǎng)需要和外網(wǎng)通信的時(shí)候，私人地址轉(zhuǎn)換成合法的global 的地址
• 由NAT轉(zhuǎn)換器（盒子）完成這種轉(zhuǎn)換
  NAT轉(zhuǎn)換器能夠轉(zhuǎn)換并且維護(hù)一個(gè)地址轉(zhuǎn)換表，以便回來的分組找到它的去處
• 當(dāng)回來的分組到達(dá)NAT轉(zhuǎn)換器的時(shí)候，它查找地址轉(zhuǎn)換表（以源端口作索引），獲得目標(biāo)機(jī)的私人地址，并轉(zhuǎn)換地之后發(fā)往目標(biāo)機(jī)

NAT 帶來的問題

• NAT違背了IP的結(jié)構(gòu)模型 –每個(gè)IP地址唯一地標(biāo)識(shí)了一臺(tái)機(jī)器
• NAT將互聯(lián)網(wǎng)改變成了“面向連接”的網(wǎng)絡(luò)，NAT轉(zhuǎn)換器維護(hù)著連接的狀態(tài)，一旦它崩潰，連接也沒有了
• NAT違背了最基本的協(xié)議分層原則
• 如果傳輸層不是采用TCP或UDP，而是采用了其它的協(xié)議，NAT將不再工作
• 有些應(yīng)用會(huì)在payload中插入IP地址，然后接收方會(huì)提取出該IP地址并使用，但是NAT轉(zhuǎn)換器對(duì)此一無所知，導(dǎo)致該類應(yīng)用不再有效
• NAT讓一個(gè)IP地址可以承載61,440（65536-4096）個(gè)私人地址（超載，PAT）

NAT/PAT的評(píng)價(jià)：

• 優(yōu)點(diǎn)
  節(jié)省了公有IP地址；
  提供了內(nèi)部網(wǎng)訪問外網(wǎng)的靈活性；
  有一定的保密性。
• 缺點(diǎn)
  影響了部分協(xié)議和應(yīng)用的通信；
  增加了網(wǎng)絡(luò)延時(shí)；
  NAT轉(zhuǎn)換設(shè)備的性能可能成為網(wǎng)絡(luò)的瓶頸；
  影響了路由追蹤工具的使用。

3.3 理解ICMP及其應(yīng)用

用來報(bào)告意外的事件或測試互聯(lián)網(wǎng)

3.3.1 ping的工作原理

• 使用ping命令（即調(diào)用ping過程）時(shí)，將向目的站點(diǎn)發(fā)送一個(gè)ICMP回聲請(qǐng)求報(bào)文（包括一些任選的數(shù)據(jù)），

• 如目的站點(diǎn)接收到該報(bào)文，必須向源站點(diǎn)發(fā)回一個(gè)ICMP回聲應(yīng)答報(bào)文，源站點(diǎn)收到應(yīng)答報(bào)文（且其中的任選數(shù)據(jù)與所發(fā)送的相同），則認(rèn)為目的站點(diǎn)是可達(dá)的，否則為不可達(dá)。

3.3.2 tracert命令

• tracert過程是通過ICMP數(shù)據(jù)報(bào)超時(shí)報(bào)文來得到一張途經(jīng)的路由器列表
• 源主機(jī)向目的主機(jī)發(fā)一個(gè)IP報(bào)文，并置TTL為1，到達(dá)第一個(gè)路由器時(shí)，TTL減1，為0，則該路由器回發(fā)一個(gè)ICMP數(shù)據(jù)報(bào)超時(shí)報(bào)文，源主機(jī)取出路由器的IP地址即為途經(jīng)的第一個(gè)路由端口地址
• 接著源主機(jī)再向目的主機(jī)發(fā)第二個(gè)IP報(bào)文，并置TTL為2，然后再發(fā)第三個(gè)、第四個(gè)IP數(shù)據(jù)報(bào)，……直至到達(dá)目的主機(jī)
• 但互聯(lián)網(wǎng)的運(yùn)行環(huán)境狀態(tài)是動(dòng)態(tài)的，每次路徑的選擇有可能不一致，所以，只有在相對(duì)較穩(wěn)定（相對(duì)變化緩慢）的網(wǎng)絡(luò)中，tracert才有意義

3.4 地址解析協(xié)議(ARP/RARP)

ARP （地址解析協(xié)議）： IP 地址-> MAC 地址
RARP （逆向地址解析協(xié)議）：MAC 地址 -> IP 地址
ARP的工作原理：

image.png

為了讓ARP的工作更加高效，下面是幾種優(yōu)化措施：

• 緩存 ARP 結(jié)果
• 在ARP請(qǐng)求中包括源機(jī)的 IP-to-MAC 地址的映射
• 每臺(tái)機(jī)器在啟動(dòng)的時(shí)候，廣播它的IP-MAC地址對(duì)

缺省網(wǎng)關(guān)（代理 ARP）

• 當(dāng)源設(shè)備需要的目的地址與自己不在同一個(gè)網(wǎng)絡(luò)時(shí)，如果源不知道目的MAC地址，它必須使用路由器的服務(wù)使它的數(shù)據(jù)達(dá)到目的，當(dāng)路由器在這種方式下使用時(shí)，稱為缺省網(wǎng)關(guān)。
• 缺省網(wǎng)關(guān)是與源設(shè)備所處的網(wǎng)段相連的路由器接口上的IP地址

ARP表：

• IP地址到MAC地址的映射表，儲(chǔ)存在存儲(chǔ)器（RAM）中，自動(dòng)維護(hù)。（掉電消失）
• 為了減少ARP請(qǐng)求的次數(shù)，每個(gè)設(shè)備擁有自己的ARP表，包括路由器。

自動(dòng)維護(hù)ARP表

• 通過廣播ARP請(qǐng)求中的源設(shè)備信息添加更新表；
• 利用自己的ARP請(qǐng)求之應(yīng)答信息來添加、更新表；
• 刪除超過一定時(shí)限的信息（有時(shí)戳）

3.5 IP地址的分配方式

IP地址的分配方式：

• 靜態(tài)分配
• 動(dòng)態(tài)分配

IP地址的動(dòng)態(tài)分配方式(RARP\Boot\pDHCP)

DHCP：動(dòng)態(tài)主機(jī)配置協(xié)議

• 可以靈活分配IP地址，節(jié)約IP地址的使用
• 使一臺(tái)主機(jī)迅速并動(dòng)態(tài)地獲取一個(gè)IP地址
• 通過DHCP獲取的 IP是租來的，可能會(huì)過期

4 擁塞控制

擁塞：當(dāng)一個(gè)子網(wǎng)或子網(wǎng)的一部分出現(xiàn)太多分組的時(shí)候，網(wǎng)絡(luò)的性能急劇下降，這就是擁塞（Congestion ）

導(dǎo)致?lián)砣囊蛩?擁塞根源：負(fù)載 > 資源)

• 輸入流量速度大于輸出線路的容量
• 慢速的處理器也可能引起擁塞，如線路容量充足，但處理器來不及處理
• 線路容量和處理器能力需要平衡

image.png

4.1 擁塞控制的通用原則

image.png

怎么知道擁塞了？ --擁塞量度

• 因?yàn)槿狈彺婵臻g而丟棄的分組百分比
• 平均隊(duì)列長度
• 超時(shí)和重傳的分組數(shù)
• 平均分組延遲
• 分組延遲的標(biāo)準(zhǔn)方差（standard deviation）

上述這些度量，數(shù)值越大表示擁塞的程度越重

4.2 怎樣解決擁塞問題

• 增加資源
  在某些點(diǎn)之間使用更多的通道增加帶寬（比如：廣深）
  把流量分散到多條路徑
  啟用空閑或備份的路由器
• 降低負(fù)載
  拒絕為某些用戶提供服務(wù)（比如：春節(jié)車票提價(jià)，限行）
  給某些用戶的服務(wù)降低等級(jí)（比如：黃金周旅游）
  讓用戶更有預(yù)見性地安排他們的需求（比如：年假制）
• image.png

4.3 擁塞控制算法：

4.3.1. 流量感知路由

在計(jì)算路由時(shí)考慮鏈路負(fù)載，把熱點(diǎn)地區(qū)的流量轉(zhuǎn)移出去。最直接的方法是吧鏈路權(quán)重設(shè)置成一個(gè)鏈路帶寬、傳輸延遲、平均排隊(duì)延遲的函數(shù)。

缺點(diǎn)：可能導(dǎo)致路由搖擺

4.3.2. 準(zhǔn)入控制：

• 防止擁塞進(jìn)一步惡化和加劇
• 基本思想：一旦出現(xiàn)擁塞信號(hào)，則不再創(chuàng)建任何虛電路，直到問題得到解決

準(zhǔn)入控制可以與流量感知相結(jié)合，允許建立新的虛電路，但是仔細(xì)選擇線路，繞開問題區(qū)域

4.3.3. 流量調(diào)節(jié)

擁堵路由器通告源機(jī)發(fā)送慢下來（抑制包）

4.3.4. 負(fù)載丟棄/載荷脫落

• 這是處理擁塞的最極端的方法
• 當(dāng)路由器收到的分組超載了，一些分組會(huì)被丟掉
• 丟掉哪些分組呢？
  • 隨機(jī)丟棄（random）
  • 丟棄新到達(dá)的 (葡萄酒策略，適合文件傳輸類)
  • 丟棄早到達(dá)的分組 (牛奶策略，適合多媒體類)
  • 丟棄不太重要的（less important ）分組（需要發(fā)送方在它們的分組中標(biāo)明優(yōu)先級(jí)）

4.3.5. 隨機(jī)早期檢測RED（防患于未然）

• 當(dāng)情況變得惡化無可救藥之前就開始丟棄分組
• 為了確定什么時(shí)候開始丟棄分組，路由器維護(hù)著最近的隊(duì)列平均長度
• 當(dāng)某條線上的隊(duì)列平均長度超過了某閾值時(shí)，該線路被認(rèn)定是擁塞的，可以采取相應(yīng)的措施
• 告訴源機(jī)關(guān)于擁塞的情況有兩種可能
  • 發(fā)送抑制分組
  • 僅僅丟棄，不做任何報(bào)告

4.4 抖動(dòng)控制

分組到達(dá)時(shí)間的變化量(標(biāo)準(zhǔn)方差 standard deviation)叫做抖動(dòng)（jitter）

如何做抖動(dòng)控制（續(xù)）

• 通過計(jì)算出沿途每一跳的期望傳輸時(shí)間，就可以控制抖動(dòng)。
  • 當(dāng)一個(gè)分組到達(dá)路由器，路由器檢查這個(gè)分組，看它是來晚了還是來早了
  • 如果分組來早了，那么它可能多停留一些時(shí)間，以便回到預(yù)定的時(shí)間點(diǎn)上
  • 如果分組來晚了，路由器應(yīng)該盡可能快地將他轉(zhuǎn)發(fā)出去
• 當(dāng)幾個(gè)分組都要使用同一根輸出線路轉(zhuǎn)發(fā)出去，哪一個(gè)分組優(yōu)先呢？
  • 路由器總是讓偏離預(yù)定時(shí)間最遠(yuǎn)的那個(gè)分組優(yōu)先轉(zhuǎn)發(fā)

5 流量整形

• 調(diào)節(jié)數(shù)據(jù)傳輸?shù)钠骄俾剩ê屯话l(fā)數(shù)據(jù)流）

算法

• 漏桶（ leaky bucket）
• 令牌桶（ token bucket）
• 其它：資源預(yù)留、準(zhǔn)入控制、分組調(diào)度等

可以減少擁塞

5.1 漏桶算法

image.png

image.png

漏桶的缺點(diǎn)

• 當(dāng)漏桶滿了之后，數(shù)據(jù)將被丟棄
• 不能大量地突發(fā)數(shù)據(jù)
  改進(jìn)：令牌桶

5.2 令牌桶算法

image.png

算法描述：

• 當(dāng)大量數(shù)據(jù)突發(fā)的時(shí)候，令牌桶算法允許輸出加快到某種程度
• 令牌桶擁有令牌（tokens），且以每△T秒產(chǎn)生一個(gè)令牌的速度往桶中輸入令牌
• 一個(gè)分組要發(fā)送的時(shí)候，它必要從桶中取出和獲取到一個(gè)令牌
• 令牌桶算法允許累積令牌，但最多可以累積n（令牌桶的容量）個(gè)令牌

和漏桶算法相比：

• 令牌桶允許突發(fā)，但是最大突發(fā)受制于令牌桶容量的限制
• 當(dāng)桶滿的時(shí)候，令牌桶算法丟掉的是令牌（不是分組）

image.png

6 互聯(lián)網(wǎng)路由

• 互聯(lián)網(wǎng)路由類似于單個(gè)子網(wǎng)內(nèi)部的路由，但是，前者比后者更加復(fù)雜一些

兩級(jí)路由算法

• 每個(gè)網(wǎng)絡(luò)內(nèi)部采用內(nèi)部網(wǎng)關(guān)協(xié)議（ IGP， interior gateway protocol ）
• 網(wǎng)絡(luò)之間使用外部網(wǎng)關(guān)協(xié)議（ BGP， exterior gateway protocol ）

互聯(lián)網(wǎng)上的每個(gè)網(wǎng)絡(luò)都是獨(dú)立于所有其他的網(wǎng)絡(luò)，所以每個(gè)網(wǎng)絡(luò)通常稱作一個(gè)自治系統(tǒng)（Autonomous System ，AS）
互聯(lián)網(wǎng)路由和網(wǎng)絡(luò)內(nèi)部路由的差別是：
互聯(lián)網(wǎng)路由可能需要跨越國際邊界，不同的法律可能會(huì)介入進(jìn)來

IP協(xié)議

IP地址：網(wǎng)絡(luò)號(hào)和主機(jī)號(hào)

• 唯一的
• 每個(gè)主機(jī)至少有一個(gè)
• 表示方法：點(diǎn)分十進(jìn)制表示

IP的任務(wù)是提供一種盡力傳送（ Best-Efforts ）的方法，將數(shù)據(jù)報(bào)從源傳送到目的

IP地址的分類：

image.png

掌握IPv4的保留地址空間

網(wǎng)絡(luò)地址：主機(jī)部分全為“0”的 IP 地址
廣播地址：主機(jī)部分全為“1”的 IP 地址

例子：

• 分析地址172.16.20.200
  分析：
  B類地址
  子網(wǎng)部分：172.16
  主機(jī)部分：20.200
  網(wǎng)絡(luò)地址：172.16.0.0
  廣播地址：172.16.255.255

保留的IP地址：

• 32位全為0，0.0.0.0
  這個(gè)主機(jī)、這個(gè)網(wǎng)絡(luò)
  Cisco路由器指定的默認(rèn)路由
• 32位全為1，255.255.255.255 Flood Broadcast（泛洪，本地）(受限的廣播,路由器并不轉(zhuǎn)發(fā)該地址的數(shù)據(jù)包）
• 主機(jī)部分全為0，如172.16.0.0 網(wǎng)絡(luò)地址
• 主機(jī)部分全為1，如172.16.255.255 廣播地址
• 127.0.0.0 Lookback Network
• 127.0.0.1 Lookback test
• 169.254.x.x 非正常地址，例如DHCP未正常開啟時(shí)候會(huì)被分配

掌握子網(wǎng)及子網(wǎng)劃分

• 局域網(wǎng)不斷增長，越來越難于管理，必須將它分割成子網(wǎng)
• 一個(gè)網(wǎng)絡(luò)被分隔成幾個(gè)部分（子網(wǎng)），但是在外界看來，該網(wǎng)絡(luò)仍被看成一個(gè)整體 (體現(xiàn)在路由表例上，就是外部的路由器只對(duì)應(yīng)一條路由）
• 這也允許不同的子網(wǎng)在一個(gè)組織內(nèi)部連接起來

子網(wǎng)掩碼

• 路由器使用子網(wǎng)掩碼決定分組往哪個(gè)子網(wǎng)轉(zhuǎn)發(fā)
• 子網(wǎng)掩碼可用點(diǎn)分十進(jìn)制表示（ 1表示網(wǎng)絡(luò)位， 0表示主機(jī)位），也可用“ /網(wǎng)絡(luò)位數(shù)+子網(wǎng)位數(shù)” 表示
  255.255.255.224
  202.10.23.102/27
• 路由器采用“ AND ”操作（目的IP和子網(wǎng)掩碼），得到目的網(wǎng)絡(luò)地址
• 使用這種機(jī)制，路由器不必記錄全部主機(jī)的IP地址，縮減了路由器的規(guī)模

子網(wǎng)規(guī)劃

• 將大網(wǎng)絡(luò)分割成小網(wǎng)絡(luò)
• 劃分子網(wǎng)實(shí)際上建立了一個(gè)由網(wǎng)絡(luò)、子網(wǎng)和主機(jī)構(gòu)成的三級(jí)層次結(jié)構(gòu)，從而降低了路由器的表空間
• 構(gòu)建子網(wǎng)是通過從網(wǎng)絡(luò)地址的主機(jī)部分借位來進(jìn)行
• 子網(wǎng)規(guī)劃將導(dǎo)致IP地址空間的損失

確定可用主機(jī)數(shù)量的公式 2n-2

借位規(guī)則：
從主機(jī)域的高位開始借位；
主機(jī)域至少保留 2 位。

可變長子網(wǎng)掩碼 (VLSM)

• VLSM允許將網(wǎng)絡(luò)空間分為大小不等的部分。
• 子網(wǎng)掩碼將依據(jù)為特定子網(wǎng)所借用的位數(shù)而變化。
• 先對(duì)網(wǎng)絡(luò)劃分子網(wǎng)，然后再將子網(wǎng)進(jìn)一步劃分子網(wǎng)。
• 根據(jù)需要重復(fù)此過程，以創(chuàng)建不同大小的子網(wǎng)

image.png

image.png

image.png

理解IP分組格式

IP分組格式：

image.png

所以IP數(shù)據(jù)報(bào)報(bào)頭的最小長度為20個(gè)字節(jié)

固定部分（前20字節(jié)）：

image.png

image.png

image.png

image.png

image.png

image.png

(8)生存時(shí)間　占8位，生存時(shí)間字段常用的的英文縮寫是TTL(Time To Live)，表明是數(shù)據(jù)報(bào)在網(wǎng)絡(luò)中的壽命。由發(fā)出數(shù)據(jù)報(bào)的源點(diǎn)設(shè)置這個(gè)字段。其目的是防止無法交付的數(shù)據(jù)報(bào)無限制地在 因特網(wǎng) 中兜圈子，因而白白消耗網(wǎng)絡(luò)資源。最初的設(shè)計(jì)是以秒作為TTL的單位。每經(jīng)過一個(gè) 路由器 時(shí)，就把TTL減去數(shù)據(jù)報(bào)在路由器消耗掉的一段時(shí)間。若數(shù)據(jù)報(bào)在路由器消耗的時(shí)間小于1秒，就把TTL值減1。當(dāng)TTL值為0時(shí)，就丟棄這個(gè)數(shù)據(jù)報(bào)。后來把TTL字段的功能改為“跳數(shù)限制”（但名稱不變）。路由器在轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)之前就把TTL值減1.若TTL值減少到零，就丟棄這個(gè)數(shù)據(jù)報(bào)，不再轉(zhuǎn)發(fā)。因此，現(xiàn)在TTL的單位不再是秒，而是跳數(shù)。TTL的意義是指明數(shù)據(jù)報(bào)在網(wǎng)絡(luò)中至多可經(jīng)過多少個(gè)路由器。顯然，數(shù)據(jù)報(bào)在網(wǎng)絡(luò)上經(jīng)過的路由器的最大數(shù)值是255.若把TTL的初始值設(shè)為1，就表示這個(gè)數(shù)據(jù)報(bào)只能在本局域網(wǎng)中傳送。

(9)用戶協(xié)議　占8位，協(xié)議字段指出此數(shù)據(jù)報(bào)攜帶的數(shù)據(jù)是使用何種協(xié)議，以便使目的主機(jī)的IP層知道應(yīng)將數(shù)據(jù)部分上交給哪個(gè)處理過程。

(10)首部檢驗(yàn)和　占16位。這個(gè)字段只檢驗(yàn)數(shù)據(jù)報(bào)的首部，但不包括數(shù)據(jù)部分。這是因?yàn)閿?shù)據(jù)報(bào)每經(jīng)過一個(gè)路由器，路由器都要重新計(jì)算一下首部檢驗(yàn)和（一些字段，如生存時(shí)間、標(biāo)志、片偏移等都可能發(fā)生變化）。不檢驗(yàn)數(shù)據(jù)部分可減少計(jì)算的工作量。

(11)源地址　占32位。

(12)目的地址　占32位。

IPV6

image.png

IPv6地址首選格式：冒分十六進(jìn)制

image.png

image.png

image.png

鏈路本地地址

image.png

image.png

image.png

image.png