互聯網IP路由的逐跳全局最優化原則-Dijkstra算法證明

把周末寫了一半的東西繼續補齊了，實現了完美的一天。
我們知道的一個事實就是IP地址實在太多了，根本就不可能統一的管理起來，無論從數據平面還 是從控制/管理平面上說都是這樣。所以，IP協議被設計出來就是可擴展的。對于IP路由來講，路由計算是逐跳進行的，當然也支持“源路由”選項，源路由就 是說數據在出發前就已經把路線規劃好了，逐跳路由是IP路由的標準形式，也就是說，IP數據包是在路上即時規劃路線的。
       我比較喜歡IP路由是因為這也是我旅行的方式，我喜歡旅行，但是我不喜歡事先訂酒店，事先規劃路線，導航等，我的方式是在路上看路牌前行，到了臨時停下的 地方之后背著行囊找住處，然后走到哪算哪，這是一種說走就走且沒有目的地的游蕩...當然，IP數據包是有目的地的。

逐跳全局最優化

IP路由是在每一臺路由器上逐跳路由的，那么就產生了一個問題，偌大一個互聯網，該怎么相信這么多逐跳路由拼接起來的一條完整的路徑確實是最優化的呢？答案顯然是確定的，問題是怎么證明它。

路由算法

書 上講，路由算法基本分為距離矢量算法和鏈路狀態算法，各自的協議代表作就是RIP和OSPF(我就是靠著這兩個找到的第一份工作)，確實是這樣，但是從這 些算法的正確性的證明過程中，你就會發現，確實是“逐跳的最優化路由真的就是全局的最優化路由”。本文中我僅僅給出基于鏈路狀態路由協議的 Dijkstra算法的證明，因為全網每臺設備的鏈路狀態數據庫都是相同的，所以它是很好理解的。

Dijkstra算法正確性證明

首先要給出Dijkstra算法正確性的證明，才能進行后續的。畢竟，Dijkstra算法本身只是指導了step by step的操作步驟，并沒沒能證明這么折騰一圈得到的最短路徑樹中的每一條路徑確實是最短的。而要想證明逐跳全局最優化原則，需要這個事實。
       下面的示意圖給出了Dijkstra算法正確性的簡單證明，詳細完備的數學證明可以參照這個思路：

逐跳全局最優化的問題

下面的示意圖點名了逐跳全局最優化的問題所在：

逐跳全局最優化的證明

下面的示意圖給出了逐跳全局最優化的簡單證明，證明方式多種多樣，我這里給出的僅僅是其中一種：

附：Dijkstra算法的貪心模型

如 果我們在地上倒上一杯水，觀察水攤開***的痕跡，就會理解Dijkstra算法，它確實是不證自明的。大自然是懶惰的，總是用最省力的方式行事，水分子在 落地那個點開始，在崎嶇不平的地上由于重力(暫時不考慮其它分子力)沿著一定的路徑到達一系列點，這些路徑一定是最短路徑。我們可以把地面的崎嶇程度視為 路徑的權值，這不就和Dijkstra算法模型一模一樣嗎？