互联网IP合全局路由优化的原则-Dijkstra算法证明

周末继续写东西的一半填补了，为了达到完美的一天。
我们知道一个事实，IP地址太多。统一管理是不可能的了，无论从控制平面从数据/管理层表示，飞机是如此。

所以。IP协议被设计为可伸缩。供IP路由术语，跳路由进行计算。当然，支持“源路由”，源路由就是说数据在出发前就已经把路线规划好了，逐跳路由是IP路由的标准形式。也就是说。IP数据包是在路上即时规划路线的。
       我比較喜欢IP路由是由于这也是我旅行的方式，我喜欢旅行，可是我不喜欢事先订酒店。事先规划路线。导航等，我的方式是在路上看路牌前行。到了暂时停下的地方之后背着行囊找住处，然后走到哪算哪，这是一种说走就走且没有目的地的游荡...当然，IP数据包是有目的地的。

逐跳全局最优化

IP路由是在每一台路由器上逐跳路由的。那么就产生了一个问题。偌大一个互联网，该怎么相信这么多逐跳路由拼接起来的一条完整的路径确实是最优化的呢？答案显然是确定的。问题是怎么证明它。

路由算法

书上讲，路由算法基本分为距离矢量算法和链路状态算法，各自的协议代表作就是RIP和OSPF(我就是靠着这两个找到的第一份工作)，确实是这样，可是从这些算法的正确性的证明过程中，你就会发现，确实是“逐跳的最优化路由真的就是全局的最优化路由”。

本文中我只给出基于链路状态路由协议的Dijkstra算法的证明，由于全网每台设备的链路状态数据库都是同样的。所以它是非常好理解的。

Dijkstra算法正确性证明

首先要给出Dijkstra算法正确性的证明。才干进行兴许的。毕竟。Dijkstra算法本身不过指导了step by step的操作步骤，并没没能证明这么折腾一圈得到的最短路径树中的每一条路径确实是最短的。

而要想证明逐跳全局最优化原则。须要这个事实。
       以下的示意图给出了Dijkstra算法正确性的简单证明，具体完备的数学证明能够參照这个思路：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG9nMjUw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

逐跳全局最优化的问题

以下的示意图点名了逐跳全局最优化的问题所在：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG9nMjUw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

逐跳全局最优化的证明

以下的示意图给出了逐跳全局最优化的简单证明。证明方式多种多样。我这里给出的不过当中一种：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG9nMjUw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

附：Dijkstra算法的贪心模型

假设我们在地上倒上一杯水，观察水摊开渗透的痕迹，就会理解Dijkstra算法。它确实是不证自明的。

大自然是懒惰的，总是用最省力的方式行事。水分子在落地那个点開始，在崎岖不平的地上由于重力(暂时不考虑其他分子力)沿着一定的路径到达一系列点，这些路径一定是最短路径。我们可以粗略地级视为权重路径，这不是和Dijkstra做同样的算法模型？