轉彎限制路由

路由算法決定數據包從網絡中的源路由器到目標路由器所遵循的路徑。設計路由算法時要重點考慮的一個方面是避免死鎖。轉彎限制路由 是一種用於mesh拓撲系列的路由算法，它通過限制算法中允許的下一方向來避免死鎖，同時確定網絡中從源節點到目標節點的路由。

圖 1：圖中顯示了輸入和輸出緩衝區都已滿的四個信道。輸出緩衝區中的所有數據包都將被轉發到下一個信道。但是由於它們的輸入緩衝區已滿，因此無法進行轉發。結果，不能再移動任何數據包。這就產生了死鎖。

產生死鎖的原因

死鎖（如圖 1 所示）是由於緩衝區或連結等網絡資源飽和而無法進一步傳輸數據包的情況。死鎖的主要原因是網絡中信道的循環獲取。 例如，考慮網絡中有四個信道。四個數據包已經填滿了這四個信道的輸入緩衝區，需要轉發到下一個信道。現在假設所有這些通道的輸出緩衝區也充滿了需要傳輸到下一個信道的數據包。如果這四個信道形成一個循環，則無法繼續傳輸數據包，因為所有通道的輸出緩衝區和輸入緩衝區都已滿。這稱為循環獲取信道，會導致死鎖。

死鎖的解決方法

死鎖可以被預防、避免、檢測和解除。 就延遲和資源而言，檢測和打破網絡中的死鎖是昂貴的。因此，簡單且低成本的解決方案是使用防止循環獲取信道的路由技術來避免死鎖。

圖 2：網絡路線中所有可能的轉彎 - 順時針和逆時針。

轉彎限制路由背後的邏輯

輪流限制路由背後的邏輯源自一個關鍵特性。若且唯若所有四個可能的順時針（或逆時針）旋轉都已發生時，才可能出現循環獲取信道的現象。這意味着可以通過至少禁止順時針轉動之一和逆時針轉動之一來避免死鎖。圖 2 顯示了非限制路由算法中所有可能的順時針和逆時針轉彎。

圖 3：XY 路由

轉彎限制路線示例

可以通過在路由算法中禁止四個可能的順時針轉彎中的至少一個和四個可能的逆時針轉彎中的至少一個來獲得轉彎限制路由。這意味着至少有 16 (4x4) 種可能的轉彎限制路由技術，因為總共有 4 個順時針轉彎和 4 個逆時針轉彎可供選擇。下面列出了其中一些技術。

圖 4：西向優先路由

圖 5：北最後路由

圖 6：負優先路由

XY 路由

XY 路由 （如圖 3 所示）限制了從 y 軸到 x 軸的所有轉向。這避免了並不一定需要的兩個逆時針和兩個順時針轉向。因為它限制了允許的轉彎方向，我們可以把它作為轉彎限制路由的示例。

西優先路由

西優先路由 （如圖 4 所示）限制所有轉向西方向（x軸負方向）的轉彎。這意味着如果在尋找路徑時需要，應首先選擇西向。

北最後路由

北最後路由 （如圖 5 所示）如果當前方向為北（y軸正方向），則不能轉向任何其他方向。這意味着如果在尋找路徑時需要，應最後選擇北方向。

負優先路由

負優先路由 （如圖6所示）禁止在上一方向為正時轉向負方向。西被認為是X維度的負方向，南被認為是Y維度的負方向。這意味着在進行任何其他轉彎之前，應在其中一個負方向上有越點。

轉彎限制路由的優點

• 與死鎖檢測和解除技術相比，避免死鎖的實現成本更低。
• 轉彎限制提供從一個節點到另一個節點的最短路徑以及非最小長度路徑作為備用，這允許繞過擁塞或故障鏈路進行路由。

例如，考慮下面的圖 7。假設有多個路由器，F1、F2 等，它們將數據包傳輸到一個擁擠但低成本的鏈路，從源路由器 S 到目標路由器 D。實施轉彎限制路由意味着現在可能會一些有從饋線路由器到路由器 S 的轉彎被限制。這些饋線路由器可能必須使用更長的路徑才能到達目的地 D，從而在一定程度上緩解從 S 到 D 的鏈路擁塞。

圖 7：相互連接的四台路由器 F1、F2、S 和 D 的拓撲結構。轉向限制可以在一定程度上緩解鏈路 SD 上的擁塞。

• 基於策略的路由
• 死鎖
• 啟發式算法