通訊網路/路由

路由

路由是將資訊資料包傳送到目的地所需經過的過程。路由是一個出乎意料的複雜任務，有多種不同的演算法被用來找到兩個點之間的最短路徑。

介紹

IP 地址基於主機和網路的概念。主機本質上是網路上任何能夠接收和傳輸 IP 資料包的裝置，例如工作站或路由器。路由是將資料從一臺主機計算機移動到另一臺主機計算機的過程。路由和橋接之間的區別在於，橋接發生在 OSI 參考模型的第 2 層（鏈路層），而路由發生在第 3 層（網路層）。路由確定透過網路的最佳路由路徑。

路由演算法

路由演算法儲存在路由器的記憶體中。路由演算法是路由環境效能的主要因素之一。路由演算法的目的是為路由器做出有關資料最佳路徑的決策。路由器使用路由演算法來計算最適合將資料從源傳輸到目的地的路徑。請注意，您無法直接選擇路由器使用的演算法。相反，您為網路選擇的路由協議決定了將使用哪種演算法。例如，雖然路由資訊協議 (RIP) 路由協議可能使用一種型別的路由演算法來幫助路由器移動資料，但開放最短路徑優先 (OSPF) 路由協議使用另一種演算法。路由演算法不可更改。更改它的唯一方法是更改路由協議。您網路的整體效能主要取決於路由演算法，因此您應該在決定在網路上實施哪個協議之前，研究每個協議使用的演算法。路由演算法主要分為兩大類：距離向量或鏈路狀態。每個名為“距離向量”的路由協議都使用距離向量演算法，而每個鏈路狀態協議都使用鏈路狀態演算法。

路由協議中的路由演算法

路由協議的工作之一是提供路由演算法計算其決策所需的資訊。這是許多協議有所不同的點。提供給演算法的資訊在不同的協議中可能不同。

路由協議從周圍環境收集有關網路和路由器的資訊，並將資訊儲存在路由器記憶體中的路由表中。路由演算法使用該表中的資訊來計算從一個網路到另一個網路的最佳路徑。計算公式中的新值，然後生成一個總和。該計算結果隨後用於確定將資訊傳送到哪裡。例如，下表說明了虛構路由環境的示例路由表。路由表中傳遞給路由演算法的資訊是透過稱為路由更新的過程由路由協議收集的。透過一系列更新，每臺路由器都會告訴其他路由器它擁有哪些資訊。最終，將建立完整的路由表。

路由器鏈路	度量
路由器 A 到路由器 B	2
路由器 B 到路由器 C	3
路由器 A 到路由器 C	6
路由器 C 到路由器 D	5

示例路由演算法指出，到達任何目的地的最佳路徑是度量值最低的路徑。度量是一個數字，用作衡量網路鏈路的標準。每個鏈路都被分配一個度量，以代表從使用線路的貨幣成本到可用頻寬的數量的任何內容。當路由器 A 接收一個從路由器 C 傳送的資料包時，路由表顯示了兩種可能的路徑供選擇。第一個選擇是將資料包從路由器 A 直接透過鏈路傳送到路由器 C。第二個選擇是將資料包從路由器 A 傳送到路由器 B，然後繼續傳送到路由器 C。路由演算法用於確定哪個選項最佳。

一些路由協議可能只向路由演算法提供一個度量，而另一些協議可能提供多達十個度量。另一方面，雖然兩個協議都可能只向演算法傳送一個度量，但該度量的來源可能在不同的協議中有所不同。一種路由協議可能會給演算法提供成本的單個度量，但該成本可能代表與使用相同度量的另一種協議不同的東西。

我們示例中的演算法指出，最佳路徑是度量值最低的路徑。因此，透過新增與每條可選鏈路相關的度量數字，我們看到，從路由器 A 到路由器 B 再到路由器 C 的路由的度量值為 5，而到路由器 C 的直接鏈路的度量值為 6。演算法選擇 A-B-C 路徑並將資訊傳送過去。

距離向量演算法

距離向量演算法使用稱為成本的度量來幫助確定到達目的地的最佳路徑。總成本最低的路徑被選為最佳路徑。

當路由器使用距離向量演算法時，每個路由器都會收集不同的成本。這些成本可以是完全任意的數字。成本也可以是動態收集的值，例如路由器在透過一條鏈路而不是另一條鏈路傳送資料包時所經歷的延遲量。所有成本都被編譯並放置在路由器的路由表中，然後由演算法用於計算任何給定網路場景的最佳路徑。

儘管有很多資源會提供關於距離向量演算法是什麼以及它們如何計算其決策的複雜數學表示，但核心概念仍然相同——透過新增網路上每條可選路徑的度量，您將得到至少一條最佳路徑。該公式如下所示

M(i,k) = min [M(i,t) + M(t,k)]

該公式指出，兩個網路之間的最佳路徑 (M(i,k)) 可以透過找到所有網路點之間路徑的最低 (min) 值來找到。讓我們再次看一下上面表格中的路由資訊。將此資訊代入公式，我們看到，從 A 到 B 再到 C 的路由仍然是最佳路徑

5(A,C) = min[2(A,B) + 3(B,C)]

而從 A 到 C 的直接路由公式如下所示

6(A,C) = min[6(A,C)]

此示例顯示了距離向量演算法如何使用傳遞給它們的資訊來做出明智的路由決策。路由器和路由協議使用的演算法不可配置，也不能修改。

距離向量演算法和鏈路狀態協議之間另一個主要區別在於，當距離向量路由協議相互更新時，整個或部分路由表（取決於更新型別）將從一臺路由器傳送到另一臺路由器。透過此過程，每臺路由器都會接觸到其他路由器表中包含的資訊，從而使每臺路由器對網路環境有更完整的瞭解，並能夠做出更好的路由決策。距離向量演算法的示例包括 RIP 和 BGP，它們是當今使用最廣泛的兩種協議。其他流行的協議，如 OSPF，是使用鏈路狀態路由演算法的協議的示例。

距離向量演算法也稱為貝爾曼-福特路由演算法和福特-福克森路由演算法。在這些演算法中，每臺路由器都有一個路由表，顯示了到任何目的地的最佳路由。下面顯示了路由器 J 的典型圖和路由表。

目的地	權重	線路
A	8	A
B	20	A
C	20	I
D	20	H
E	17	I
F	30	I
G	18	H
H	12	H
I	10	I
J	0	N/A
K	6	K
L	15	K

該表顯示，如果路由器 J 想要將資料包傳送到路由器 D，它應該首先將資料包傳送到路由器 H。當資料包到達路由器 H 時，當前路由器會檢查自己的表並決定如何將資料包傳送到 D。在距離向量演算法中，每臺路由器都必須遵循以下步驟

1. 它計算直接與其連線的鏈路的權重並將資訊儲存到其表中。

2. 在特定的時間段內，路由器將其表傳送到其鄰居路由器（而不是所有路由器）並接收其每個鄰居的路由表。

3. 基於路由器從其鄰居路由表中接收的資訊，它更新自己的路由表。

讓我們再看一個例子（下面顯示的圖形）。

每條鏈路的成本都設定為 1。因此，最低成本路徑只是跳數最少的路徑。下表表示每個節點關於到所有其他節點距離的知識

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F	G
A	0	1	1	$\infty$	1	1	$\infty$
B	1	0	1	$\infty$	$\infty$	$\infty$	$\infty$
C	1	1	0	1	$\infty$	$\infty$	$\infty$
D	$\infty$	$\infty$	1	0	$\infty$	$\infty$	1
E	1	$\infty$	$\infty$	$\infty$	0	$\infty$	$\infty$
F	1	$\infty$	$\infty$	$\infty$	$\infty$	0	1
G	$\infty$	$\infty$	$\infty$	1	$\infty$	1	0

最初，每個節點將其直接連線的鄰居的成本設定為 1，將其餘所有節點的成本設定為無窮大。以下是節點 A 的初始路由表

目的地	成本	下一跳
B	1	B
C	1	C
D	$\infty$	-
E	1	E
F	1	F
G	$\infty$	-

在下一步中，每個節點都向其直接連線的鄰居傳送一條訊息。該訊息包含該節點的個人距離列表。例如，節點 F 告訴節點 A 它可以以 1 的成本到達節點 G；節點 A 也知道它可以以 1 的成本到達 F，因此它將這些成本加起來以獲得透過 F 到達 G 的成本。由於 2 小於當前的無窮大成本，因此節點 A 記錄它可以以 2 的成本透過 F 到達 G。節點 A 從 C 處得知節點 B 可以從 C 處以 1 的成本到達，因此它得出結論，透過 C 到達 B 的成本為 2。由於這比當前到達 B 的成本（1）更差，因此忽略了新資訊。節點 A 的最終路由表如下所示

目的地	成本	下一跳
B	1	B
C	1	C
D	2	C
E	1	E
F	1	F
G	2	F

將一致的路由資訊傳播到所有節點的過程稱為收斂。下表顯示了從每個節點到所有其他節點的最終成本集

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F	G
A	0	1	1	2	1	1	2
B	1	0	1	2	2	2	3
C	1	1	0	1	2	2	2
D	2	2	1	0	3	2	1
E	1	2	2	3	0	2	3
F	1	2	2	2	2	0	1
G	2	3	2	1	3	1	0

每條鏈路的成本都設定為 1。因此，最低成本路徑只是跳數最少的路徑。

距離向量演算法的一個問題稱為“無限計數”。讓我們透過一個例子來檢查以下問題

考慮一個網路，其圖形如下所示。D 和網路其他部分之間只有一條鏈路。

帶有向量

d [A][A] = 0 d [A][B] = 1 d [A][C] = 2 d [A][D] = 3

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	1
D	3	2	1	0

現在 C 到 D 的鏈路崩潰了，所以 cost [C][D] = ∞ C 以前將任何地址為 D 的資料包直接轉發到 CD 鏈路，但現在鏈路已斷開，因此 C 必須重新計算其距離向量（並做出新的選擇以轉發到 D 的資料包）- 同樣，D 也必須更新其向量。在更新 C 和 D 處的向量後，我們有

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

C 將 B 視為到達 D 的最佳路由，成本為 1 + 2，因此 C 將新向量傳送到 B。B 瞭解到它以前透過 C 傳送到 D 的選擇現在成本更高，因此 B 應該重新計算其向量。

	A	B	C	D
A	0	1	2	3
B	1	0	1	4
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

B 的觀點是路由到 D 可以透過 A 或 C 進行，成本相同 - B 傳送更新的向量。A 和 C 都從 B 處獲得更新的向量，並瞭解到它們到 D 的首選路由現在成本更高，因此它們重新計算自己的向量。

	A	B	C	D
A	0	1	2	5
B	1	0	1	4
C	2	1	0	5
D	$\infty$	$\infty$	$\infty$	0

然後 A 和 C 傳送它們的向量，B 必須再次更新其向量，向 A 和 C 傳送另一輪，得到。

	A	B	C	D
A	0	1	2	7
B	1	0	1	6
C	2	1	0	7
D	$\infty$	$\infty$	$\infty$	0

請注意，路由表非常緩慢地收斂到以下事實

d [x][D] = ∞ for x = A 或 x = B 或 x = C

這個過程會迴圈，直到所有節點都發現到 D 的鏈路的權重為無窮大。這樣，專家們說距離向量演算法的收斂速度很慢。總之，距離向量演算法不是健壯的。解決此問題的一種方法是讓路由器只向非目的地獨佔鏈路的鄰居傳送資訊。例如，在本例中，B 不應向 C 傳送有關 D 的任何資訊，因為 C 是到達 D 的唯一途徑。

鏈路狀態演算法

距離向量演算法和鏈路狀態演算法都偏愛成本最低的路徑。但是，鏈路狀態協議以更本地化的方式工作。雖然執行距離向量演算法的路由器將計算任何給定資料包的端到端路徑，但鏈路狀態協議將計算與最直接鏈路相關的路徑。也就是說，距離向量演算法將計算網路 A 和網路 C 之間的最低度量，而鏈路狀態協議將將其計算為兩個不同的路徑，即 A 到 B 和 B 到 C。對於更大的環境，此過程非常高效。鏈路狀態演算法使路由器能夠專注於自己的鏈路和介面。網路上的任何一臺路由器都只知道直接與其連線的路由器和網路（或其自身鏈路的狀態）。在更大的環境中，這意味著路由器將使用更少的處理能力來計算複雜的路徑。路由器只需要知道它的哪個直接介面可以最快地將資訊傳送到需要去的地方。下一臺路由器將重複此過程，直到資訊到達其目的地。這種本地化路由過程的另一個優勢是協議可以維護更小的路由表。由於鏈路狀態協議只維護其直接介面的路由資訊，因此路由表包含的資訊比可能包含多個路由器資訊的距離向量協議少得多。與距離向量協議類似，鏈路狀態協議需要更新來彼此共享資訊。這些路由更新稱為鏈路狀態通告 (LSA)，它們在路由器鏈路狀態發生變化時發生。當某個特定鏈路不可用（狀態發生變化）時，路由器會透過環境傳送更新，提醒與其直接連線的所有路由器。

在鏈路狀態演算法中，每臺路由器都必須遵循以下步驟

1. 識別與之物理連線的路由器並獲取它們的 IP 地址 當路由器開始工作時，它首先透過網路傳送一個“HELLO”資料包。接收此資料包的每臺路由器都會回覆一條包含其 IP 地址的訊息。

2. 路由器測量鄰居路由器的延遲時間（或網路的其他任何重要引數，例如平均流量）。為了做到這一點，路由器透過網路傳送回聲資料包。接收這些資料包的每臺路由器都會回覆一個回聲回覆資料包。透過將往返時間除以 2，路由器可以計算延遲時間。延遲時間包括傳輸時間和處理時間 - 資料包到達目的地所需的時間以及接收器處理它並回復所需的時間。

3. 將其資訊廣播到網路中供其他路由器使用，並接收其他路由器的資訊。在此步驟中，所有路由器都共享其知識並將資訊廣播給彼此。這樣，每臺路由器都可以瞭解網路的結構和狀態。

4. 路由器使用適當的演算法來識別網路中兩個節點之間的最佳路由。在此步驟中，路由器選擇到每個節點的最佳路由。它們使用一個演算法（例如 Dijkstra 最短路徑演算法）來做到這一點。在該演算法中，路由器根據從其他路由器收集的資訊，構建一個網路圖。該圖顯示了網路中路由器的位置以及它們彼此之間的鏈路。每個鏈路都標有一個稱為權重或成本的數字。此數字是延遲時間、平均流量以及有時只是節點之間跳數的函式。例如，如果節點和目的地之間有兩條鏈路，路由器將選擇權重最低的鏈路。

Dijkstra 演算法

Dijkstra 演算法透過以下步驟進行

1. 路由器構建網路圖。然後它識別源節點和目標節點，例如 R1 和 R2。路由器然後構建一個矩陣，稱為“鄰接矩陣”。在鄰接矩陣中，座標表示權重。例如，[i, j] 是節點 Ri 和 Rj 之間鏈路的權重。如果 Ri 和 Rj 之間沒有直接鏈路，則該權重被識別為“無窮大”。
2. 路由器然後為網路上的每個節點構建一個狀態記錄。該記錄包含以下欄位
   • 前驅欄位 - 顯示前一個節點。
   • 長度欄位 - 顯示從源節點到該節點的權重總和。
   • 標籤欄位 - 顯示節點的狀態；每個節點都有一種狀態模式："永久"或"暫定"。
3. 在下一步中，路由器初始化狀態記錄的引數（對於所有節點）並將它們的標籤設定為“暫定”，並將它們的長度設定為“無窮大”。
4. 在此步驟中，路由器設定一個 T-節點。例如，如果 R1 是要作為源 T-節點，則路由器將 R1 的標籤更改為“永久”。一旦標籤更改為“永久”，它將永遠不會再更改。
5. 路由器更新所有直接連結到源 T-節點的暫定節點的狀態記錄。
6. 路由器遍歷所有暫定節點，並選擇權重到 R1 最小的那個節點。然後，該節點就是目標 T-節點。
7. 如果新的 T-節點不是 R2（預期目標），則路由器返回步驟 5。
8. 如果該節點是 R2，則路由器從狀態記錄中提取其上一個節點，並一直這樣做，直到它到達 R1。此節點列表顯示了從 R1 到 R2 的最佳路線。

Dijkstra 演算法示例

讓我們找到路由器 A 和 E 之間的最佳路線。它們之間有六條可能的路線（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），並且很明顯 ABDE 是最佳路線，因為它的權重最低。但生活並不總是那麼容易，我們有一些複雜的情況，我們必須使用演算法來找到最佳路線。

1. 源節點 (A) 已被選為 T-節點，因此它的標籤是永久的（永久節點用實心圓表示，T-節點用 -> 符號表示）。

2. 在此步驟中，已更改直接連結到 T-節點 (B、C) 的暫定節點的狀態記錄。此外，由於 B 的權重較小，因此它已被選為 T-節點，並且它的標籤已更改為永久。

3. 與步驟 2 相似，已更改與 T-節點 (D、E) 有直接連結的暫定節點的狀態記錄。由於路由器 D 的權重較小，因此它已被選為 T-節點，並且它的標籤已更改為永久。

4. 由於我們沒有任何暫定節點，因此我們只需識別下一個 T-節點。由於節點 E 的權重最小，因此它已被選為 T-節點。

現在我們必須識別路線。E 的上一個節點是節點 D，D 的上一個節點是節點 B，B 的上一個節點是節點 A。因此，我們確定最佳路線是 ABDE。在這種情況下，總權重為 4 (1+2+1)。該演算法執行良好，但它非常複雜，路由器可能需要很長時間才能處理它。這會導致網路效率下降。我們應該在這裡注意的另一點是，如果路由器向其他路由器提供錯誤資訊，則所有路由決策將無效。

下一個示例顯示瞭如何在網路中的所有節點之間找到最佳路線。該示例使用 **最短路徑 Dijkstra 演算法**。請考慮以下顯示的網路

讓我們使用 Dijkstra 演算法查詢 A 將用於向網路上的任何節點傳輸資料的路線。Dijkstra 路由演算法在下表中表示

		B	C	D	E	F	G	H	I
步驟 1	A	2-A	3-A	5-A	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
步驟 2	AB		3-A	5-A	7-B	9-B	$\infty$	$\infty$	$\infty$
步驟 3	ABC			4-C	4-C	9-B	$\infty$	$\infty$	$\infty$
步驟 4	ABCD				4-C	9-B	$\infty$	11-D	$\infty$
步驟 5	ABCDE					8-E	12-E	7-E	$\infty$
步驟 6	ABCDEH					8-E	12-E		11-H
步驟 7	ABCDEHF						10-F		11-H
步驟 8	ABCDEHFG								11-H
步驟 9	ABCDEHFGI

這是網路在所有更新後看起來的樣子，顯示了節點之間的最短路線

內部路由

網際網路中的資料包路由分為兩大類：內部路由和外部路由。內部路由發生在獨立網路系統內部或內部。在 TCP/IP 術語中，這些獨立的網路系統稱為自治系統。在自治系統 (AS) 內，使用自治系統管理選擇的內部路由協議交換路由資訊。另一方面，外部路由協議用於自治系統之間。內部路由協議確定到每個目的地的“最佳”路線，並在網路上的系統之間分發路由資訊。有幾種內部協議

- 路由資訊協議 (RIP) 是 UNIX 系統上最常用的內部協議。RIP 使用距離向量演算法，該演算法選擇具有最低“跳數”(度量) 的路線作為最佳路線。RIP 跳數表示資料必須透過多少閘道器才能到達其目的地。RIP 假設最佳路線是使用最少閘道器的路線。

- Hello 是一種協議，它使用延遲作為選擇最佳路線的決定因素。延遲是資料報從源到目的地往返所需的時間。

- 中間系統到中間系統 (IS-IS) 是來自 OSI 協議套件的內部路由協議。它是一種鏈路狀態協議。它是在 T1 NSFNET 骨幹網上使用的內部路由協議。

- 開放最短路徑優先 (OSPF) 是為 TCP/IP 開發的另一種鏈路狀態協議。它適用於非常大的網路，並提供比 RIP 更好的幾個優勢。

路由資訊協議 (RIP)

RIP（路由資訊協議）是閘道器和主機之間交換路由資訊的標準。它是一種距離向量協議。RIP 作為“內部閘道器協議”最為有用。網路被組織為“自治系統”的集合。每個自治系統都有自己的路由技術，對於不同的自治系統，這種技術可能完全不同。在自治系統內使用的路由協議被稱為內部閘道器協議或“IGP”。路由資訊協議 (RIP) 旨在與使用相當同質技術的中等規模網路一起使用。因此，它適合作為許多校園和使用序列線路（速度變化不大）的區域網路的內部閘道器協議 (IGP)。它不適合在更復雜的環境中使用。RIP2 源自 RIP，是路由資訊協議 (RIP) 的擴充套件，旨在擴充套件 RIP 訊息中承載的有用資訊量並增加一定程度的安全性。RIP2 是一種基於 UDP 的協議。

使 RIP 正常工作的是一個路由資料庫，它儲存有關計算機之間最快速路線的資訊，一個更新過程，使每個路由器能夠告訴其他路由器從其角度來看哪條路線最快，以及一個更新演算法，使每個路由器能夠使用從相鄰路由器傳達的最快速路線來更新其資料庫

**資料庫** - 給定網路上的每個 RIP 路由器都儲存一個數據庫，該資料庫為該網路中的每臺計算機儲存以下資訊

IP 地址 - 計算機的網際網路協議地址。

閘道器 - 傳送到該 IP 地址的訊息的最佳閘道器。

距離 - 此路由器與能夠直接傳送訊息到該 IP 地址的路由器之間的路由器數量。

路線更改標誌 - 表示此資訊已更改的標誌，其他路由器使用它來更新自己的資料庫。

計時器 - 各種計時器。

**演算法** - RIP 演算法的工作原理如下

更新 - 每隔一段時間，每個路由器都會向其直接連線到的所有其他路由器傳送一條更新訊息，描述其路由資料庫。有些路由器會每隔 30 秒傳送一次此訊息，以便網路始終擁有最新資訊，以便在計算機和路由器啟動和關閉網路時快速適應變化。RIP 和 RIP2 的協議結構如下所示

RIP 和 RIP2 的協議結構如下所示

8 位	16 位	32 位
命令	版本	未使用
地址族識別符號		路由標籤（僅適用於 RIP2；RIP 為 0）
IP 地址
子網掩碼（僅適用於 RIP2；RIP 為 0）
下一跳（僅適用於 RIP2；RIP 為 0）
度量

**命令** - 命令欄位用於指定資料報的目的。有五個命令：請求、響應、Traceon（已過時）、Traceoff（已過時）和保留。

**版本** - RIP 版本號。當前版本為 2。

**地址族識別符號** - 指示在此特定條目中指定了哪種型別的地址。這是因為 RIP2 可能會承載幾種不同協議的路由資訊。IP 的地址族識別符號為 2。

**路由標籤** - 分配給路由的屬性，必須保留並使用路由重新通告。路由標籤提供了一種方法來區分內部 RIP 路由（RIP 路由域內網路的路由）和外部 RIP 路由，這些路由可能是從 EGP 或其他 IGP 匯入的。

**IP 地址** - 目的地 IP 地址。

子網掩碼 - 應用於 IP 地址的值，以產生地址的非主機部分。如果為零，則沒有為此條目包含子網掩碼。

**下一跳** - 應將傳送到此路由條目指定的目的地的資料包轉發到的直接下一跳 IP 地址。

**度量** - 表示從主機到該目的地的資料報的總成本。此度量是與要遍歷以到達目的地的網路相關的成本的總和。

開放最短路徑優先協議 (OSPF)

OSPF 是一種內部閘道器協議，用於連線屬於單個自治系統的路由器。OSPF 使用鏈路狀態技術，其中路由器彼此傳送有關它們與其他路由器之間的直接連線和鏈路的資訊。每個 OSPF 路由器都維護一個描述自治系統拓撲的相同資料庫。從該資料庫中，透過構建最短路徑樹來計算路由表。OSPF 在拓撲發生變化時會快速重新計算路由，並使用最少的路由協議流量。提供了區域路由功能，從而可以提供額外的路由保護級別並減少路由協議流量。此外，所有 OSPF 路由協議交換都經過身份驗證。OSPF 根據 IP 資料包報頭中找到的目標 IP 地址來路由 IP 資料包。IP 資料包按原樣路由 - 它們在穿過自治系統時不會封裝在任何其他協議報頭中。OSPF 允許將網路集分組在一起。這種分組稱為區域。區域的拓撲對自治系統的其餘部分隱藏。這種資訊隱藏可以顯著減少路由流量。此外，區域內的路由僅由區域自身的拓撲決定，從而使區域免受錯誤路由資料的侵害。

OSPF 演算法的工作原理如下

啟動 - 當路由器開啟時，它會向所有鄰居傳送 Hello 資料包，接收它們的 Hello 資料包，並透過與同意同步的相鄰路由器同步資料庫來建立路由連線。

更新 - 每隔一定時間，每個路由器都會向所有其他路由器傳送一條名為“鏈路狀態”的更新訊息，其中描述了其路由資料庫，以便所有路由器都具有對本地網路拓撲的相同描述。

最短路徑樹 - 然後每個路由器計算一個稱為“最短路徑樹”的數學資料結構，該結構描述了到每個目標地址的最短路徑，因此指示了傳送到每個通訊的最接近路由器；換句話說 - “開放最短路徑優先”。

OSPF（開放最短路徑優先版本 2）的協議結構如下所示

8 位	16 位	24 位
版本號	資料包型別	資料包長度
路由器 ID
區域 ID
校驗和		AuType
身份驗證

版本號 - 協議版本號（當前為 2）。

資料包型別 - 有效型別如下：1 Hello 2 資料庫描述 3 鏈路狀態請求 4 鏈路狀態更新 5 鏈路狀態確認。

資料包長度 - 協議資料包的長度（以位元組為單位）。此長度包括標準 OSPF 標頭。

路由器 ID - 資料包源的路由器 ID。在 OSPF 中，路由協議資料包的源和目標是（潛在）相鄰關係的兩端。

區域 ID - 標識此資料包所屬的區域。所有 OSPF 資料包都與單個區域相關聯。大多數只傳播單跳。

校驗和 - 資料包整個內容的標準 IP 校驗和，從 OSPF 資料包標頭開始，但不包括 64 位身份驗證欄位。

AuType - 標識要用於資料包的身份驗證方案。

身份驗證 - 用於身份驗證方案的 64 位欄位。

中間系統到中間系統路由協議（IS-IS）

中間系統到中間系統 (IS-IS) 是一種鏈路狀態協議，其中 IS（路由器）基於單個度量交換路由資訊以確定網路拓撲。它在 TCP/IP 網路中的行為類似於開放最短路徑優先 (OSPF)。在 IS-IS 網路中，有終端系統、中間系統、區域和域。終端系統是使用者裝置。中間系統是路由器。路由器被組織成稱為“區域”的本地組，多個區域被分組到一個“域”中。IS-IS 主要用於提供域內路由或區域內的路由。IS-IS 與 CLNP、ES-IS 和 IDRP 協同工作，提供整個網路的完整路由。IS-IS 路由利用兩級層次路由。級別 1 - 路由器瞭解其區域內的拓撲結構，包括所有路由器和主機，但它們不知道其區域之外的路由器或目標的身份。級別 1 路由器將所有指向其區域之外的目標的流量轉發到其區域內的級別 2 路由器，該路由器瞭解級別 2 拓撲。級別 2 路由器不需要了解任何級別 1 區域內的拓撲，除非級別 2 路由器也可能是一個區域內的級別 1 路由器。IS-IS 已被改編為承載 IP 網路資訊，稱為整合 IS-IS。整合 IS-IS 具有現代路由協議中最重要的特徵：它支援 VLSM 並快速收斂。它還可以擴充套件以支援非常大的網路。IS-IS 地址有兩種型別：網路服務訪問點 (NSAP) - NSAP 地址標識網路層服務，每個執行的服務一個。網路實體標題 (NET) - NET 地址標識網路層實體或程序，而不是服務。裝置可能擁有兩種型別地址中的多個地址。但是 NET 應該是唯一的，並且 NSAP 的系統 ID 部分必須對每個系統都唯一。IS-IS（中間系統到中間系統路由協議）的協議結構如下所示

8 位				16 位
域內路由協議鑑別符				長度指示器
版本/協議 ID 擴充套件				ID 長度
R	R	R	PDU 型別	版本
保留				最大區域地址

域內路由協議鑑別符 - 分配給此協議的網路層協議識別符號

長度指示器 - 固定報頭的長度（以八位位元組為單位）。

版本/協議 ID 擴充套件 - 等於 1。

ID 長度 - 此路由域中使用的 NSAP 地址和 NET 的 ID 欄位長度。

R - 保留位。

PDU 型別 - PDU 的型別。位 6、7 和 8 保留。

版本 - 等於 1。

最大區域地址 - 此中間系統區域允許的區域地址數量。

IS-IS 的 NSAP 格式如下所示

<-IDP->		<-DSP->
		<-HO-DSP->
AFI	IDI	由 IDI 欄位中標識的授權機構分配的內容
<-區域地址->			<-ID->	<-SEL->

IDP - 初始域部分

AFI - 授權和格式識別符號（1 位元組）；提供有關 IDI 和 DSP 欄位的結構和內容的資訊。

IDI - 初始域識別符號（可變長度）

DSP - 域特定部分

HO-DSP - 高階域特定部分

區域地址（可變）

ID - 系統 ID 1-8 位元組

SEL - n 選擇器（1 位元組值，其功能類似於 Internet 協議中的埠號）。

外部路由

外部路由發生在自治系統之間，是服務提供商和其他大型或複雜網路關心的問題。基本可路由元素是自治系統。雖然可能存在許多不同的內部路由方案，但單個外部路由系統管理著全球網際網路，主要基於 BGP-4 外部路由協議。

邊界閘道器協議 (BGP)

邊界閘道器協議 (BGP) 確保資料包無論當前網路狀況如何都能到達其目標網路。BGP 本質上是一種距離向量演算法，但有一些額外的變化。首先，BGP 路由器與它直接通訊的其他 BGP 路由器建立連線。它所做的第一件事是下載每個相鄰路由器的整個路由表。之後，它只與其他路由器交換短得多的更新訊息。BGP 路由器傳送和接收更新訊息以指示到達具有給定 IP 地址的計算機的首選路徑的更改。如果路由器決定更新自己的路由表，因為此新路徑更好，那麼它將隨後將此資訊傳播到它連線的所有其他相鄰 BGP 路由器，而它們反過來將決定是否更新自己的表並將資訊進一步傳播出去。

BGP 在埠 179 上使用 TCP/IP 協議建立連線。它具有強大的安全功能，包括在 BGP 路由器之間所有通訊中包含數字簽名。每個 BGP 路由器都包含一個路由資訊庫 (RIB)，其中包含該路由器維護的路由資訊。RIB 包含三種類型的資訊

• Adj-RIBs-In - 相鄰路由器傳送的未經編輯的路由資訊。
• Loc-RIB - 路由器實際使用的路由資訊，從 Adj-RIBs-In 開發而來。
• Adj-RIBs-Out - 路由器選擇傳送給相鄰路由器的資訊。

BGP 路由器使用四種類型的訊息交換資訊

• 開啟 - 用於與相鄰路由器開啟初始連線。
• 更新 - 這些訊息完成了大部分工作，在相鄰路由器之間交換路由資訊，幷包含以下資訊之一
  • 撤回的路由 - 路由器不再可以路由訊息到的計算機的 IP 地址。
  • 路徑 - IP 地址的新首選路由。此路徑包含兩部分資訊 - IP 地址和用於路由到該地址的目標訊息的路徑中下一個路由器的地址。
• 通知 - 用於指示錯誤，例如接收到的錯誤或不可讀的訊息，並且之後立即關閉與相鄰路由器的連線。
• 保持活動 - 每個 BGP 路由器大約每 30 秒向每個相鄰路由器傳送一個 19 位元組的 Keepalive 訊息，以告知它們它仍然可以執行，並且每三秒不超過一次。如果任何路由器在設定的時間內沒有從相鄰路由器收到 Keepalive 訊息，它將關閉與該路由器的連線，並將其從路由資訊庫中刪除，修復它認為對網路造成的損害。

路由訊息是網際網路上優先順序最高的流量，每個 BGP 路由器都優先考慮它們，優先於所有其他流量。這是有道理的 - 如果路由資訊無法透過，那麼其他任何資訊也無法透過。

BGP 演算法在 BGP 路由器從相鄰路由器收到更新訊息後執行，幷包含以下三個步驟，這些步驟針對相鄰路由器傳送的每個 IP 地址執行

• 更新 - 如果更新訊息中 IP 地址的路徑資訊與之前從該路由器接收的資訊不同，那麼 Adj-RIBs-In 資料庫將使用最新資訊更新。
• 決策 - 如果是新資訊，則會執行一個決策過程，以確定在所有當前記錄在 Adj-RIBs-In 資料庫中的 BGP 路由器中，哪個路由器對更新訊息中的 IP 地址具有最佳路由路徑。該演算法沒有強制要求，BGP 管理員可以為決策過程設定本地策略標準，例如與每個相鄰路由器通訊需要多長時間，以及每個相鄰路由器與路徑中的下一個路由器通訊需要多長時間。如果此決策過程所選擇的最佳路徑與當前記錄在 Loc-RIB 資料庫中的路徑不同，則更新資料庫。
• 傳播 - 如果決策過程發現了一條更好的路徑，則 Adj-RIBs-Out 資料庫也會更新，路由器會向所有相鄰的 BGP 路由器傳送更新訊息，告訴它們關於更好的路徑。然後，每個相鄰路由器依次執行自己的 BGP 演算法，決定是否更新其路由資料庫，然後依次將所有新的和改進的路徑傳播到相鄰路由器。

BGP 演算法執行的另一個重要功能是消除路由資訊中的迴圈。例如，當路由器 A 認為路由器 B 是傳送某些計算機訊息的最佳路徑，而 B 認為最佳路徑是透過 C，但 C 認為最佳路徑是返回 A 時，就會發生路由迴圈。如果允許這種型別的路由迴圈發生，那麼任何透過路由器 A、B 或 C 傳遞到該計算機的訊息將永遠在它們之間迴圈，無法傳遞訊息，並且會消耗越來越多的網路資源。BGP 演算法會捕獲並停止任何此類迴圈。

分層路由

在鏈路狀態和距離向量演算法中，每個路由器都必須儲存一些關於其他路由器的資訊。當網路規模擴大時，網路中路由器的數量會增加。因此，路由表的規模也會增加，路由器無法像以前那樣高效地處理網路流量。分層路由用於克服這個問題。讓我們來考察一個例子。

距離向量演算法用於找到節點之間的最佳路徑。在下面的情況下，網路中的每個節點都必須儲存一個包含 17 條記錄的路由表。

以下是 A 的典型圖和路由表

目的地	線路	權重
A	N/A	N/A
B	B	1
C	C	1
D	B	2
E	B	3
F	B	3
G	B	4
H	B	5
I	C	5
J	C	6
K	C	5
L	C	4
M	C	4
N	C	3
O	C	4
P	C	2
Q	C	3

在分層路由中，路由器被分類為稱為區域的組。每個路由器只擁有其自身區域中路由器的資訊，而沒有其他區域中路由器的資訊。這樣，路由器在表中只需為每個區域儲存一條記錄。在這個例子中，我們將我們的網路分為五個區域（見下圖）。

目的地	線路	權重
A	N/A	N/A
B	B	1
C	C	1
區域 2	B	2
區域 3	C	4
區域 4	C	3
區域 5	C	2

如果 A 要向區域 2（D、E、F 或 G）中的任何路由器傳送資料包，則將資料包傳送到 B，依此類推。如您所見，在這種型別的路由中，表可以被概括，從而提高了網路效率。上面的例子展示了雙層分層路由。我們也可以使用三層或四層分層路由。在三層分層路由中，網路被分為若干個叢集。每個叢集由若干個區域組成，每個區域包含若干個路由器。分層路由被廣泛用於網際網路路由，並利用了多種路由協議。

總結

在距離向量演算法中，將你所知道的全部資訊傳送給你的鄰居，而鏈路狀態演算法則將你鄰居的資訊傳送給所有人。

鏈路狀態演算法的訊息大小很小，而距離向量演算法的訊息大小可能很大。

鏈路狀態演算法的訊息交換量很大，而距離向量演算法的訊息交換量只限於鄰居。

收斂速度

– 鏈路狀態演算法：很快

– 距離向量演算法：使用觸發更新時很快

空間需求

– 鏈路狀態演算法維護整個拓撲

– 距離向量演算法只維護鄰居狀態

魯棒性

• 鏈路狀態演算法可以廣播不正確/損壞的 LSP - 區域性問題

• 距離向量演算法可以向所有目的地釋出不正確的路徑 - 不正確的計算會蔓延到整個網路

練習

1. 對於下面給定的網路，給出全域性距離向量表，當

a) 每個節點只知道到其直接鄰居的距離

b) 每個節點已將其在先前步驟中所擁有的資訊報告給其直接鄰居

c) 步驟 b) 再次發生

2. 對於練習 1 中的網路，展示鏈路狀態演算法如何為節點 D 構建路由向量表。

3. 對於下圖給定的網路，給出全域性距離向量表，當

a) 每個節點只知道到其直接鄰居的距離

b) 每個節點已將其在先前步驟中所擁有的資訊報告給其直接鄰居

c) 步驟 b) 再次發生

4. 假設我們在一個所有鏈路成本都為 1 的網路中，有如下所示的節點 A 和 F 的轉發表。給出與這些表一致的最小網路圖。

對於節點 A，我們有

節點	成本	下一跳
B	1	B
C	1	C
D	2	B
E	3	C
F	2	C

對於節點 F，我們有

節點	成本	下一跳
A	2	C
B	3	C
C	1	C
D	2	C
E	1	E

5. 對於下面的網路，使用最短路徑 Dijkstra 演算法找到從節點 A 作為源頭的最小成本路由。

答案

1.

a)

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F
A	0	$\infty$	3	8	$\infty$	$\infty$
B	$\infty$	0	$\infty$	$\infty$	2	$\infty$
C	3	$\infty$	0	$\infty$	1	6
D	8	$\infty$	$\infty$	0	2	$\infty$
E	$\infty$	2	1	2	0	$\infty$
F	$\infty$	$\infty$	6	$\infty$	$\infty$	0

b)

c)

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F
A	0	6	3	6	4	9
B	6	0	3	4	2	9
C	3	3	0	3	1	6
D	6	4	3	0	2	9
E	4	2	1	2	0	7
F	9	9	6	9	7	0

2.

D	已確認	暫定
1.	(D,0,-)
2.	(D,0,-)	(A,8,A) (E,2,E)
3.	(D,0,-) (E,2,E) (C,3,E)	(A,8,A) (B,4,E)
4.	(D,0,-) (E,2,E) (C,3,E)	(A,6,E) (B,4,E) (F,9,E)
5.	(D,0,-) (E,2,E) (C,3,E) (B,4,E)	(A,6,E) (F,9,E)
6.	previous + (A,6,E)
7.	previous + (F,9,E)

3.

a)

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F
A	0	2	$\infty$	5	$\infty$	$\infty$
B	2	0	2	$\infty$	1	$\infty$
C	$\infty$	2	0	2	$\infty$	3
D	5	$\infty$	2	0	$\infty$	$\infty$
E	$\infty$	1	$\infty$	$\infty$	0	3
F	$\infty$	$\infty$	3	$\infty$	3	0

b)

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F
A	0	2	4	5	3	$\infty$
B	2	0	2	4	1	4
C	4	2	0	2	3	3
D	5	4	2	0	$\infty$	5
E	3	1	3	$\infty$	0	3
F	$\infty$	4	3	5	3	0

c)

資訊 儲存在節點	到達節點的距離
	A	B	C	D	E	F
A	0	2	4	5	3	6
B	2	0	2	4	1	4
C	4	2	0	2	3	3
D	5	4	2	0	5	5
E	3	1	3	5	0	3
F	6	4	3	5	3	0

4.

5.

步驟 1

步驟 2

步驟 3

步驟 4

步驟 5

參考文獻

• http://e-books.amagrammer.net/
• 計算機網路，第 3 版，2003 年，Peterson 和 Davie
• http://www.eng.ucy.ac.cy/christos/Courses/ECE360/Lectures.htm