文章插图
图2 节点S在距离向量下的全局状态例1：考虑图1的网路，链路状态由(频宽、时延、花费)给定 。图2给出了节点S在距离向量下的全局状态 。（3）分级路由算法假定网路节点分级，每个节点了解聚合的全局状态，即自己所在範围内的情况，而对远处的上级节点只了解大致情况 。即每一物理节点保持聚合的网路影像(见例2) 。
文章插图
图3 分级网路例2：图3给出一个分级网路模型 。图(a)表示一个实际的网路，有29个节点；图(b)示出其第一级节点，共7个；图(c)示出第二级节点共3个，该物理网路经过聚合可以变成图(d)；而从节点A、a、1来看整个网路则如图(e)所示 。按对路由的要求网路路由按对路由的要求来分，可以分为尽力而为路由和基于服务质量路由 。尽力而为路由是面向连线或带动态性能的无连线，以保证公平性、总吞吐量和平均回响时间为目标，在当前的网路环境下来选择最优路径 。而基于服务质量的路由是对各流的包基于服务质量要求选择可用路径的过程，它面向连线，带资源预留，以满足各流的连线要求，减少呼叫阻塞 。因此，它着重在满足约束，希望连线的数据传输不受其它连线的动态流量的影响 。问题是网路永远是动态的，节点对全局网路服务质量状态的了解不精确、不实时，对路由的确定与预计就未见得完全正确 。服务质量路由的代价主要包括两方面：一方面是计算开销 。因为它需要更加複杂和频繁的路由计算 。另一方面则是协定开销，因为它要分散式地提供和刷新与路由选择有关的网路资源状态信息 。路由选择计算何时进行路由选择计算?一般来说是当每一次请求来到时触发路由选择 。但是，如果在两次状态刷新之间，收到许多请求，也许事先计算好路由更加有效 。当然也可以在收到状态刷新信息时计算路由 。同时，路由选择必须有灵活性，以免由于路由而造成某些路径拥塞、某些路径又很空闲 。状态刷新的触发也可以选择不同的时机 。譬如现在的状态比原来变化超过50%就触发刷新，或者是，将可用频宽按大小分级，跳了一级就触发刷新 。也可以周期性地定时触发 。刷新内容包括刷新讯息的大小、通报的指标值的类型等都要在协定中规定 。各种刷新方案各有优劣 。刷新越及时，路由需要的网路状态信息就越精确，但刷新太频繁，增加网路负担 。要在两个极端中折衷 。在IPv6协定环境下，更多的地址和报头信息也会有助于网路路由 。单播路由算法单播路由是指目的节点只有一个的路由 。以剩余频宽和剩余快取空间为服务质量目标的路由选择是一类基于链路信息的路由，所选路径一般是根据路径上的瓶颈链路状态来决定的 。例如图1中路径
文章插图
的频宽是1，因为其瓶颈链路(i，j)的频宽是1 。这一类路由可分为链路最优路由和链路约束路由 。这两类基本路由问题可以用Dijkstra或Bellman-Ford多项式複杂性的算法解决 。另一方面，以时延、时延抖动和花费为服务质量目标的路由选择是另一类所谓基于路径信息的路由 。例如图1中
文章插图
的路径时延是10，它是路径上各链路时延之和 。从而引出另外两类基本路由问题：路径最优路由和路径约束路由 。它们也可以用多项式複杂性的算法解决 。对于许多实际套用，路由不但对链路有要求，也对路径有要求，或者是对链路有多个要求，或者对路径有多个要求 。例如最宽约束最小时延路由就是要求瓶颈链路最宽，而且路径时延最小 。又如频宽约束和快取约束路由，如此等等，可以派生出许多组合的路由问题 。其中只有两类有意义的NP难问题，即路径约束路径最优路由(PCPO)和多路径约束路由(MPC) 。譬如时延约束最小花费路由，时延和时延抖动约束路由 。若所有指标(除一个以外)全有界，或者全相关，则多项式时间可解 。否则，这两类问题是NP难的 。典型的单播路由算法有： 源路由算法如果路由既有频宽约束，又有时延约束，源路由算法的複杂性就会增加 。分散式路由算法分式式路由算法把源路由算法的计算开销分散到各个节点上，各个节点只需要了解局部的信息，作出局部的路径决策 。这个算法一般用来找最短的最宽路径(瓶颈频宽最大的路径)，但当不同节点的状态信息有矛盾时，该路由算法可能产生循环路由 。分级路由算法当今网际网路的显着特徵是大型，而且天天在变化 。分级路由恰恰是用来解决大型互连网源路由可扩展性问题的 。对于ATM网路由的专用网路间接口标準(PNNI)就是分级的，每一个节点只保存一部分全局状态，许多节点集被聚合为逻辑节点 。所以，这种聚合的全局状态的大小不过是整个全局状态大小的对数 。因此，分级路由算法既能保持某些源路由算法的优点，又有许多分散式路由算法的优越性 。因为路由计算由许多节点承担，分级路由算法先从源节点的聚合全局状态出发，从最高层开始逐步下走，直到第一层 。确定了源节点所在最高层节点内的路由之后，交给下一个最高层节点的边界节点去确定在其内的路由，如此等等，直到目的节点 。不难想像，路由算法的这种简化，必然带来路由质量的代价 。聚合信息的不精确性严重影响路由的质量 。考虑图3(e)，很难估计从A、a、1到C中节点的时延，因为C的内部结构被隐藏了，并且，从A、c中的不同的节点到C中不同节点的时延可以是很不相同的，但在聚合的状态中只有一个时延值 。所以，基于聚合信息的时延值是很不精确的 。如果有多个服务质量约束，问题就更複杂 。按比例路由选最短路径可以最小化资源利用，但这些被选路径由于常常被选上，而负载过重 。选最轻负载路径可以平衡网路负载，但可能不是最短路径，因而浪费更多资源 。另外，要求网路中节点保持精确的实时的服务质量状态是不现实的 。事实上，保持精确的实时的服务质量状态只能靠及时更新，目前无法靠预测 。更新时间太长，所得状态不精确；太短，开销又太大 。选择最好路径还有同步的问题，一次刷新以后，空闲的链路会拥塞，而再一次刷新以后又会变得空闲 。基于策略的路由边界网关协定(BGP)是网际网路域间路由协定 。它允许自治系统独立地定义自己的路由策略，这就给网路路由提供了个性和灵活性 。但是，同时也产生稳定性和收敛性的问题 。有例子指出，基于策略的路由可能产生循环路由和路由振荡，这已经不光是一个路由的问题，还是一个协定的问题 。多播路由算法多播路由的问题是：给定源节点S和目的节点集R、约束集C，也许还有一个最优目标，求最好的可行树，覆盖s和R的所有节点，满足约束C 。例如在多播情况下，频宽最优的路由要求树的瓶颈链路频宽最大，时延约束路由则要求从传送者到所有目的节点的端到端延迟都小于一个给定值 。着名的斯坦(Steiner)树问题就是找花销最小的树，也就是最小花销多播路由问题 。带约束的斯坦树问题也就是时延约束最小花销多播路由问题 。这都是NP难的 。时延和时延抖动双约束的多播路由问题也是NP难的 。只有当所有指标(除一个以外)全有界，或者全相关，才会有多项式时间可解 。多播的源路由算法基于多播链路状态协定(MOSPF)，该协定是单播链路状态协定(OSFP)的扩展 。每一节点除了保存全局状态之外，还保存路由域内每一个多播组的成员信息 。从而使最短路径多播路由可用Dijkstra算法解决，时延约束多播路由问题也较容易解决 。