交換機、路由器、網橋和區域網/路由器/路由基礎

什麼是路由？

路由是在網際網路中將資訊從源頭移動到目的地的過程。在此過程中必須遇到至少一箇中間節點。路由和橋接看起來很相似，但兩者之間的主要區別在於橋接發生在 OSI 參考模型的第 2 層（鏈路層），而路由發生在第 3 層（網路層）。路由和橋接之間的重要區別之一是，第 3 層地址是按層次結構分配的，因此路由器可以有一個規則來允許它路由到數千或數百萬個地址的整個地址範圍。這在處理網際網路規模時是一個重要的優勢，因為網際網路上的主機數量太多（並且新增和刪除速度太快），以至於任何路由器都無法知道網際網路上所有主機的地址。

路由器在網路層中承擔著資訊路由的角色。路由器是網路層的核心。首先我們來看看路由器的體系結構、資料報在路由器中的處理，然後我們將學習路由演算法。

路由器的體系結構

路由器將包含以下元件

輸入埠

輸入埠執行多個功能。物理層功能由線路終結單元執行。協議解封裝由資料鏈路處理執行。輸入埠還執行查詢和轉發功能，以便從路由器交換結構的適當輸出端口出來的資料包被轉發出去。控制資料包（如攜帶 RIP、OSPF 等路由協議資訊的）被轉發到路由處理器。輸入埠在輸出線路繁忙時還會執行輸入排隊。

輸出埠

輸出埠將來自交換結構的資料包轉發到相應的輸出線路。它執行與輸入埠完全相反的物理和資料鏈路功能。輸出埠還執行來自交換結構的資料包排隊。

路由處理器

路由處理器執行路由協議。它維護路由資訊和轉發表。它還在路由器內部執行網路管理功能。

交換結構

交換結構的工作是將資料包移動到特定的埠。交換可以透過多種方式完成

• 透過記憶體交換：最簡單、最容易的路由器，輸出埠和輸入埠之間的交換在 CPU（路由器處理器）的直接控制下完成。每當資料包到達輸入埠時，路由處理器就會透過中斷得知。然後它將傳入資料包從輸入緩衝區複製到處理器記憶體。處理器然後提取目標地址，從相應的轉發表中查詢，並將資料包複製到輸出埠的緩衝區。在現代路由器中，目標地址的查詢和資料包儲存（交換）到相應記憶體位置的操作由處理器的輸入線路卡完成。
• 透過匯流排交換：輸入埠直接將資料包透過共享匯流排傳輸到輸出埠，無需路由處理器的干預。由於匯流排是共享的，因此一次只能傳輸一個數據包。如果匯流排繁忙，則傳入資料包必須在佇列中等待。路由器的頻寬受共享匯流排的限制，因為每個資料包都必須穿過單個匯流排。示例：匯流排交換 CISCO-1900、3-COM’s care builder5。
• 透過互連網路交換：為了克服共享匯流排的頻寬問題，使用了交叉連線交換網路。在交叉連線交換網路中，輸入埠和輸出埠透過水平和垂直匯流排連線。如果我們有 N 個輸入埠和 N 個輸出埠，則需要 2N 根匯流排來連線它們。要將資料包從輸入埠傳輸到相應的輸出埠，資料包沿著水平匯流排移動，直到它與通向目標埠的垂直匯流排交叉。如果垂直匯流排空閒，則傳輸資料包。但如果垂直匯流排繁忙，因為其他一些輸入線路正在傳輸資料包到同一個目標埠，則資料包將被阻塞並排隊在相同的輸入埠。

處理 IP 資料報

傳入輸入埠的資料包被儲存在佇列中，等待處理。當處理開始時，首先處理 IP 頭。執行錯誤校驗和以識別傳輸中的錯誤。如果沒有錯誤，則檢查目標 IP 地址欄位。如果目標地址是本地主機，則考慮協議 UDP、TCP 或 ICMP 等，資料欄位將傳遞給相應的模組。

如果目標 IP 地址不是本地主機，則它將在其路由表中檢查目標 IP 地址。路由表包含應將資料包轉發到的下一個路由器的地址。然後，對傳出的資料包執行輸出操作，例如其 TTL 欄位必須減少 1，並且重新計算校驗和位，並將資料包轉發到通向相應目的地的輸出埠。如果輸出埠繁忙，則資料包必須在輸出佇列中等待。

輸出埠的資料包排程程式必須從佇列中選擇資料包進行傳輸。資料包的選擇可以基於先到先服務（FCFS）或優先順序或等待公平排隊 (WFQ)，它在為傳輸排隊的資料包的不同端到端連線之間“公平地”共享出站鏈路。對於服務質量，資料包排程起著至關重要的作用。如果傳入資料報包含路由資訊，則將資料包傳送到路由協議，該協議將相應地修改路由表條目。

路由演算法

現在我們將考慮不同的路由演算法。有兩種型別的協議用於將資訊從源頭傳輸到目的地。

路由協議與被路由協議

路由協議用於在路由器之間傳遞使用者流量，例如 IP 或 IPX。路由資料包包含足夠的資訊，使路由器能夠傳遞流量。路由協議定義欄位以及如何使用這些欄位。

路由協議包括

• 網際網路協議
  • Telnet
  • 遠端過程呼叫 (RPC)
  • SNMP
  • SMTP
• Novell IPX
• 開放式系統互連網路協議
• DECnet
• Appletalk
• Banyan Vines
• 施樂網路系統 (XNS)

路由協議允許路由器收集和共享路由資訊以維護和更新路由表，而路由表反過來用於查詢到達目的地的最有效路線。

路由協議包括

• 路由資訊協議 (RIP 和 RIP II)
• 開放式最短路徑優先 (OSPF)
• 中間系統到中間系統 (IS-IS)
• 內部閘道器路由協議 (IGRP)
• 思科的增強型內部閘道器路由協議 (EIGRP)
• 邊界閘道器協議 (BGP)

路由演算法的設計目標

路由演算法具有以下一個或多個設計目標

• 最優性: 這是路由協議搜尋並獲取最佳路線的能力。路由度量用於查詢最佳路由器。跳數或延遲可用於查詢最佳路徑。應優先選擇跳數更少或延遲最小的路徑作為最佳路線。
• 簡單性和低開銷: 路由演算法的設計也儘可能簡單。路由演算法必須高效地提供其功能，並將軟體開銷降至最低。效率在軟體實現路由演算法必須在物理資源有限的計算機上執行或處理大量路由時尤為重要。
• 健壯性和穩定性: 路由協議應該在異常或不可預見的情況下正確執行，例如硬體故障、高負載條件和錯誤實現。路由協議的這一特性稱為健壯性。最好的路由演算法通常是那些經受住了時間考驗並在各種網路條件下證明穩定的演算法。
• 快速收斂: 路由演算法必須快速收斂。收斂是所有路由器就最佳路線達成一致的過程。在網路中，當網路事件導致路由中斷或變得可用，或者鏈路成本發生變化時，路由器會分發路由更新訊息，這會導致網路中的其他路由器重新計算最佳路線，並最終導致網路中的其他路由器就這些路線達成一致。
• 靈活性: 路由演算法也應該具有靈活性。它們應該快速準確地適應各種網路環境。

路由演算法的分類

路由演算法主要分為兩種型別

• 靜態路由: 在靜態路由演算法中，資料包遵循的路線始終保持不變。當路線變化非常緩慢時，使用靜態路由演算法。在這種網路中，網路管理員預先計算路由表，資料包在兩個目的地之間採取的路徑始終是已知的，並且可以精確地控制。
  • 優點
    • 可預測性: 由於網路管理員預先計算路由表，因此資料包在兩個目的地之間採取的路徑始終是已知的，並且可以精確地控制。
    • 路由器或網路鏈路無開銷: 在靜態路由中，不需要所有路由器都定期傳送包含可達性資訊的更新，因此路由器或網路鏈路的開銷很低。
    • 簡單性: 小型網路的配置很容易。
  • 缺點
    • 缺乏可擴充套件性: 計算少量主機和路由器的靜態路由很容易。但對於較大的網路，查詢靜態路由變得很麻煩，並可能導致錯誤。
    • 如果網路段移動或新增: 要實施更改，您需要更新網路上每個路由器的配置。如果您錯過了一個，在最好的情況下，連線到該路由器的段將無法到達已移動或新增的段。在最壞的情況下，您將建立一個影響許多路由器的路由迴圈。
    • 它無法適應網路中的故障: 如果使用靜態路由的網路中的鏈路出現故障，那麼即使有可用的備用鏈路，路由器也不會知道要使用它。
• 動態路由: 機器可以透過路由協議相互通訊並構建路由表。然後路由器將資料包轉發到下一個跳躍點，該跳躍點更靠近目的地。使用動態路由，路線變化更快。定期傳送網路更新，以便如果鏈路成本發生變化，網路上的所有路由器都會知道，並將相應地更改其路由表。
  • 優點
    • 可擴充套件性和適應性: 動態路由網路可以更快地增長，並且在規模更大時不會變得難以管理。它能夠適應這種增長帶來的網路拓撲變化。
    • 適應網路中的故障: 在動態路由中，路由器透過與其他路由器通訊來了解網路拓撲。每個路由器都會宣佈其存在。它還會向網路上的其他路由器宣佈其可用的路線。因此，如果您添加了新的路由器，或者向現有路由器添加了其他段，其他路由器將聽到新增的內容，並相應地調整其路由表。
  • 缺點
    • 複雜性增加: 在動態路由中，它必須定期傳送關於拓撲的通訊資訊的更新。路由器必須準確地確定它必須傳送什麼資訊。當路由器從其他路由器瞭解網路資訊時，正確適應網路變化非常困難，它必須準備刪除舊的或不可用的路由，這會增加更多複雜性。
    • 線路和路由器的開銷: 路由器定期向其他路由器傳送關於網路拓撲的通訊資訊包。這些資料包不包含使用者資訊，只包含路由器所需的資訊，因此這僅僅是線路和路由器的額外開銷。

動態路由協議的分類

第一種分類基於協議的預期使用位置: 在您的網路和另一個網路之間，或在您的網路內: 這就是內部和外部之間的區別。第二種分類與協議承載的資訊型別以及每個路由器如何做出關於如何填寫其路由表的決定有關，即鏈路狀態與距離向量。

鏈路狀態路由

在鏈路狀態協議中，路由器提供有關其附近網路拓撲的資訊，而不提供有關它知道如何到達的目的地資訊。此資訊包括它所連線的網路段或鏈路的列表，以及這些鏈路的狀態（正常執行或未正常執行）。然後將此資訊廣播到整個網路。由於在整個網路中廣播的資訊，每個路由器都可以構建自己對網路當前狀態的影像。由於每個路由器都看到相同的資訊，因此所有這些影像都應該相同。從這個影像中，每個路由器計算其到所有目的地的最佳路徑，並使用此資訊填充其路由表。現在我們將看到稱為迪傑斯特拉演算法的鏈路狀態演算法。

符號及其含義如下

• $N$ 表示圖中所有節點的集合。
• $l(i,j)$ 表示從節點 $i$ 到節點 $j$ 的鏈路成本，它們都在 $N$ 中。如果兩個節點沒有直接連線，則 $l(i,j)=\infty$。該演算法最通用的形式不需要 $l(i,j)\neq l(j,i)$，但為了簡化起見，我們假設它們相等。
• $s$ 是執行演算法以找到到所有其他節點的最短路徑的節點。
• $M$ 表示到目前為止，該演算法已將節點合併到 $N$ 中，以找到到所有其他節點的最短路徑。
• $C(n)$ 是從源節點 $s$ 到目標節點 $n$ 的路徑成本。

演算法定義

在實際中，每個路由器維護兩個列表，稱為 Tentative 和 Confirmed。這兩個列表都包含一組 (Destination, Cost, Nexthop) 格式的條目。

該演算法的工作原理如下

1. 將 Confirmed 列表初始化為一個關於我自己的條目；該條目成本為 0。
2. 對於之前步驟中剛剛新增到 Confirmed 列表中的節點，稱其為節點 Next，選擇其 LSP。
3. 對於 Next 的每個鄰居 (Neighbor)，計算到達此鄰居的成本 (Cost)，作為從我到 Next 的成本和從 Next 到鄰居的成本之和。
   1. 如果鄰居當前既不在 Confirmed 列表上也不在 Tentative 列表上，則將 (Neighbor, Cost, NextHop) 新增到 Tentative 列表，其中 NextHop 是我到達 Next 所要走的路線。
   2. 如果鄰居當前在 Tentative 列表上，並且 Cost 小於鄰居當前列出的成本，則用 (Neighbor, Cost, NextHop) 替換當前條目，其中 NextHop 是我到達 Next 所要走的路線。
4. 如果 Tentative 列表為空，則停止。否則，從 Tentative 列表中選擇成本最低的條目，將其移動到 Confirmed 列表，並返回步驟 2。

列表中成本最低的條目，將其移動到 Confirmed 列表，並返回步驟 2。

[演算法來自 Computer Networks a system approach – Peterson 和 Davie。]

現在讓我們看一個例子：考慮下面描繪的網路。

為 A 生成路由表的步驟如下

步驟	Confirmed	Tentative	註釋
1	( A,0,-)		由於 A 是 Confirmed 列表中唯一的新的成員，所以檢視它的 LSP。
2	(A,0,-)	(B,9,B) (C,3,C) (D,8,D)	A 的 LSP 表示我們可以透過 B 訪問 B，成本為 9，這比任何其他列表中的成本都低，C 和 D 也是如此。
3	(A,0,-) (C,3,C)	(B,9,B) (D,8,D)	將 Tentative 中成本最低的成員 (C) 放入 Confirmed 列表。接下來，檢查新確認的成員 (C) 的 LSP
4	(A,0,-) (C,3,C)	(D,4,C)	透過 C 訪問 E 的成本為 4，因此替換 (B, infinity,-)。
5	(A,0,-) (C,3,C) (D,4,C)	(B,6,E) (D,6,E)	透過 E 訪問 B 的成本為 6，因此替換 (B, 9, B)。
6	(A,0,-) (C,3,C) (D,4,C) (B,6,E)		唯一剩下的節點是 D，再次執行步驟 2 到 6，我們將透過 E 從 A 到 D 的距離設定為 6，按照演算法操作。因此，在下一次迭代中，新增 (D,6,E)
7	(A,0,-) (C,3,C) (D,4,C) (B,6,E) (D,6,E)		我們完成了。現在已經知道了到所有目的地的最短路徑。

距離向量路由

距離向量演算法是迭代的、非同步的、分散式的。在距離向量中，每個節點都會從一個或多個直接連線的鄰居收到一些資訊。然後執行一些計算，並可能將計算結果分發給它的鄰居。因此它是分散式的。它是互動式的，因為這種交換資訊的過程會持續下去，直到鄰居之間不再交換資訊為止。

令 $dx(y)$ 是從節點 $x$ 到節點 y 的最小成本路徑的成本。最小成本由 Bellman-Ford 方程描述

$Dx(y)=\min v\left\{C(x,V)+dv(y)\right\}$

其中公式中的 min v 是對 x 的所有鄰居取最小值。從 x 到 v 行進後，再從 v 到 y 選擇最短路徑，從 x 到 y 的最短路徑將是 C(x, V) + dv(y)。當我們開始前往某個鄰居 v 時，從 x 到 y 的最小成本是在所有鄰居 v 上取 C(x, V) + dv(y) 的最小值。

在距離向量演算法中，每個節點 x 都維護路由資料。它應該維護

1. 連線到鄰居的每條鏈路的成本，即對於連線節點 v，它應該知道 C(x,v)。
2. 它還維護其路由表，這實際上是 x 對其到 N 中所有目的地 y 的成本的估計。
3. 它還維護其每個鄰居的距離向量。即 Dv = [Dv(y): y in N]

在分散式非同步演算法中，每個節點都會定期向其每個鄰居傳送距離向量的副本。當節點 x 收到其鄰居的距離向量時，它會儲存該向量並更新其距離向量，如下所示：

$Dx(y)=\min v\left\{C(x,v)+Dv(y)\right\}{\text{for each node }}y{\text{ in }}N$

當節點更新其距離向量時，它會將其傳送到其鄰居。鄰居會執行相同的操作，此過程會持續進行，直到每個節點都沒有資訊要傳送。

距離向量演算法 [來自 kurose] 如下所示

在每個節點 x 上

讓我們考慮以下示例：網路拓撲結構如下所示

現在我們將看看在步驟 1 後構建 R8 的路由表的步驟：在步驟 2 後：在步驟 3 後：這就是解決方案。對於節點 R8，現在路由表包含以下內容。

目標	下一跳	到目標的成本
R1	R5	5
R2	R5	4
R3	R3	4
R4	R5	5
R5	R5	2
R6	R6	2
R7	R7	3

無窮大計數問題

“網路中壞訊息傳播很慢”。假設 R1、R2、R3 和 R4 是以以下方式連線的四個路由器。

這些路由器要從它們自己到路由器 R4 的路由資訊是 R1 R2 R3 3、R2 2、R3 1、R4。假設 R4 失敗。那麼由於 R3 和 R4 之間沒有直接路徑，因此 R3 到 R4 的距離變為無窮大。但是在下一次資料交換中，R3 會發現 R2 有一條到 R4 的路徑，跳數為 2，因此它會將自己的條目從無窮大更新為 2 + 1 = 3，即 (3,R3)。在第二次資料交換中，R2 會發現 R1 和 R2 都到 R4 的距離為 3，因此它會將自己對 R4 的條目更新為 3 + 1 = 4，即 (4, R3)。在第三次資料交換中，路由器 R1 會將自己的條目更改為 4 + 1 = 5，即 ( 5, R2)。此過程將繼續增加距離。以下是對此的總結表格。

交換	R1	R2	R3
0	3, R2	2, R3	1, R4
1	3, R2	2, R3	3, R3
2	3, R2	4, R3	3, R3
3	5, R2	4, R3	5, R3
… 無限計數 …

無窮大計數問題的解決方案

定義最大計數

例如，在 RFC 1058 [2] 中，將最大計數定義為 16。這意味著如果一切其他方法都失敗，則無限計數將在第 16 次迭代時停止。

分隔範圍

使用分隔範圍。分隔範圍意味著如果節點 A 透過節點 B 瞭解了到節點 C 的路由，則節點 A 不會在路由更新期間將 C 的距離向量傳送到節點 B。

中毒反向

中毒反向是與分隔範圍一起使用的附加技術。分隔範圍經過修改，以便節點不會不傳送路由資料，而是傳送資料，但將鏈路成本設定為無窮大。帶有中毒反向的分隔範圍可防止僅涉及兩個路由器的路由迴圈。對於涉及同一鏈路上更多路由器的迴圈，帶有中毒反向的分隔範圍將不足。