A Minimum Delay Routing Algorithm Using Distributed Computation 论文笔记
Published:
本文介绍了一种在网络中为每个节点建立路由参数的分布式算法，可以保证每条信息的平均延时会收敛至所有路由算法的最小平均延时。此外，本文介绍的算法还可以保证路径不会成环。
路由分配问题是当时网络研究最热门的领域之一。路由问题可以分为静态路由（static routing）、准静态路由（quasi-static routing）和动态路由（dynamic routing），而本文主要关注准静态路由的分布式算法。
所谓准静态路由，是指一个网络正在运行中，但是随着时间的变化会有新的连接被建立或者旧的连接被废除，因此至少需要为新的连接建立路由，并且有时也会更新已有连接的路由。此外，在很长的时间尺度内，还可能有网络链路和节点的增加或者失效。
对于准静态问题最普遍的算法是中心化算法，选择网络中一个特殊节点去计算所有的路由。这种策略看上去十分简单，但是也有一定的问题。比如，需要有一个准则让网络中所有节点向中心控制节点发送更新信息，还需要有一个准则让控制节点向所有节点发送路由决策。此外，网络中突然有节点或者链路失效时的处理也相当重要。
模型的数学表示
下面介绍模型的一些记号：
- $ r_i(j) $表示从节点 $i$ 进入网络，并且目的地为节点 $j$ 的期望流量（$bits/s$)。
- $t_i(j)$表示从节点 $i$ 至节点 $j$ 的所有流量，并不一定是从节点 $i$ 开始。
- $\phi_{ik}(j)$表示从节点流量$t_i(j)$中从链路$(i,k)$走的比例（$\phi_{i,k}(j)=0$ for $(i, k) \notin L,$ $\phi_{i,k}(j)=0$ for $ i=j$)。
- $f_{ik}$表示链路$(i,k)$上的期望流量（$bits/s$）。
- $D_{ik}$表示链路$(i,k)$上的单位时间期望网络包数量乘以每个包的延时，且$D_{ik}$仅为$f_{ik}$的函数。
由于节点流量$t_i(j)$是从此节点输入网络的流量加上所有路由经过 $i$ 节点的流量，故
\[t_i(j)=r_i(j)+\Sigma _l t_l(j)\phi_{li}(j)\] \[f_{ik}=\Sigma_j t_i(j)\phi_{ik}(j)\]对于任意的路由策略，方程 (1) (2)均成立。本文则对每个节点独立选择其路由变量$\phi_{ik}(j)$的分布式路由算法更感兴趣，由本文对于$\Phi$更严谨的定义，可以得出下面的结论：如果一个网络的输入集合 $r$ 和路由变量集合 $\Phi$ 给定，那么 $t$ 可以通过方程 (1) 唯一确定。所以，任意一个的路由策略可以给出集合$t, \Phi, f$，任意的分布式算法选择了$\Phi$后可以唯一确定一组集合 $t$ 和 $f$。
下面考虑网络中的延时问题，网络中的总延时（每个包的期望延时$\times$单位时间内到达的总网络包数）以用下式计算
\(D_T=\Sigma_{i,k}D_{ik}(f_{ik})\) 由于网络包到达速率与路由算法无关，则可以通过选择合适的路由变量 $\Phi$ 来最小化$D_T$，从而使得单位包的延时最小化。
下面考虑总延时的偏导，假设输入流量$r_i(j)$上有一个$增量$\epsilon，那么会直接导致相邻链路的数据增加，并且会导致所有邻居节点的流量也有一个增加，即
\(\frac{\partial D_T}{\partial r_i(j)} = \Sigma_k \phi_{ik}(j)\left[ D_{ik}'(f_{ik})+\frac{\partial D_T}{\partial r_k(j)} \right]\) 假设路由参数$\phi_{ik}(j)$有一个增量$\epsilon$，那么链路$(i,k)$上的流量会直接增加，并且 $k$ 节点的流量也会间接增加，即
\[\frac{\partial D_T}{\partial \phi_{ik}(j)} = t_i(j) \left[ D_{ik}'(f_ik) + \frac{\partial D_T}{\partial r_k(j)} \right]\]路由算法
路由算法的核心思想可以概括为：每个节点必须逐步地减小边际延时（$D_{ik}(f_{ik})+\partial D_T/\partial r_k(j)$）大的路由变量，并且增大边际延时小的路由变量。
路由算法具体来说，可以分为两个部分：计算边际延时的协议和更新路由变量 $\Phi$ 的算法。
由于每个节点可以估计链路流量$f_{ik}$，故而可以估计出延时函数$D_{ik}(f_{ik})$，从而可以计算出边际延时$D_{ik}’(f_ik)$。对于每个目标节点 $j$ ，每个节点 $i$ 等待至它收到了下游邻居发送来的$\partial D_T/\partial r_k(j)$，随后通过公式 (4) 计算$\partial D_T/\partial r_i(j)$，并将结果广播至节点 $i$ 的所有邻居节点。
路由变量的更新算法如下：在每次迭代时，将路由变量集合映射至一个新的集合$\phi^1=A(\phi)$。其中算法A的目的为减少经过非最优链路的流量比例，同时增加经过最优链路的流量比例，具体定义如下
对于$k \in B_i(j)$，
\(\phi_{ik}^1(j)=0, \Delta_{ik}(j)=0\) 对于$k \notin B_i(j)$，定义
\[a_{ik}(j)=D_{ik}'(f_{ik}) + \frac{\partial D_T}{\partial r_k(j)} - \min \limits_{m\notin B_i(j)}\left[D_{im}'(f_{im}) +\frac{\partial D_T}{\partial r_m(j)} \right]\] \[\Delta_{ik}(j)=\min \left[\phi_{ik}(j), \frac{\eta a_{ik}(j)}{t_i(j)}\right]\] 其中 $\eta$ 是算法A的一个尺度参数，令$k_{min}(i,j)$为达到（7）式最小值的m的值，那么定义
\[\phi_{i k}^{1}(j)=\left\{\begin{array}{l}{\phi_{i k}(j)-\Delta_{i k}(j)}, &k\neq k_{min}(i,j) \\ {\phi_{i k}(j)+\sum \limits_{k \neq k_{\min }(i, j)} \Delta_{i k}(j)} , &k=k_{min}(i,j)\end{array}\right.\]准静态路由中的应用（有待进一步研究）
对于稳定的输入和连接，文中给出了算法A最终会收敛至最小平均延时的严格证明。但是还需要通过进一步的研究，使文中介绍的路由算法可以应用在准静态路由问题上。关于算法能否足够快的适应统计特性的改变仍需要进一步研究，并且，算法应该从什么样的路由参数 $\Phi$ 开始迭代也是一个开放性的问题。除此之外，链路和节点的失效问题则更为复杂，作者认为需要通过更高层的协议来解决这一问题，因为路由数据无论如何也无法传输至网络不连通的部分。
总结
文中介绍了一种针对准静态路由问题的分布式算法，算法根据邻居节点周期性更新的数据来计算每个节点自己的路由参数。作者首先介绍了所有路由算法通用的数学符号和理论公式，随后给出了针对稳定输入流量和静态网络的分布式算法，但是并没有讨论算法会如何适应网络中的变化。作者认为分布式算法在适应网络变化和鲁棒性上有很大的优势，将会是路由算法的未来。
另外，文中介绍的算法和ARPANET中的算法十分类似。主要区别在于ARPANET致力于最小化单个包的延时，而不考虑其他包的延时，但是本文的算法致力于最小化网络中所有包的平均延时。这正是用户最优和整个系统最优的矛盾，而现在的网络应该是兼顾这两者的。
最后文中介绍的算法还是可以保证路由是无环的，这是当时的其他路由算法不具备的性质。这一性质除了可以降低网络中的延时外，还可以简化更高层次的网络协议，并且可以防止死锁在节点信息更新时的出现。