下一代高速广域网对实时流要求面向连结的路由。在运输层连结(呼叫)意味着终端用户之间的逻辑联系及正确有序的数据投递。在网络层，连结意味着一条包含开关和链路的网络路径。同一连结的数据包沿路径按先进先出(FIFO)顺序传送。基于服务质量路由的约束包括链路约束、路径约束、树约束、时延约束等，而带宽则包括链路带宽及CPU带宽(节点把数据泵到链路上的最大速率)。

解这一问题的基础算法是Dijkstra算法和Bellman-Ford算法。Dijkstra算法是图论中寻找最短路径的算法，它实际上求出从源节点到系统中所有节点的最短路径。把它应用到网络路由，就嫌有点浪费，因为网络路由只要求从源节点到目的节点的最短路径。Bellman-Ford算法是寻找最短路径的分布式算法，允许边的权是负的，看来适合网络路由。但是，各节点的同步是一个问题。在不同步的情况下就可能得不到最优解。

网络路由有多种分类。

按网络性质可分为多计算机系统路由、有线网络路由和无线网络路由。计算机系统路由针对一种特定的拓扑结构，例如超立方体、网格，在某些节点或链路故障的情况下寻找最优通路。这些想法实质上与因特网的路由非常类似。但是，今天，一个多计算机系统也许是一个超级大型机，用以太网连接。再考虑到任意的拓扑结构，问题就更复杂了。

网络路由按通信方式分，可以分为单播路由(即端到端的路由)、多播路由(即端到目的节点集中的每一个节点的路由)及Anycast路由(即端到目的节点集中的任一个节点的路由)。

网络路由按路由算法来分，可以分为源路由算法、分布式路由算法和分级路由算法。

（1）源路由算法假定每个节点了解整个网络的全局状态。全局状态用链路状态协议通过广播获得，或用距离向量协议，用邻节点周期性交换距离向量获得。当要发送消息时，源节点就决定了整条路径。

（2）分布式路由算法假定每个节点只了解它的邻节点的情况，即网络局部状态，包括排队延迟、传播延迟、剩余带宽等，根据路径的要求，只决定下一跳应走向哪里(见例1)。

例1：考虑图1的网络，链路状态由(带宽、时延、花费)给定。图2给出了节点S在距离向量下的全局状态。

（3）分级路由算法假定网络节点分级，每个节点了解聚合的全局状态，即自己所在范围内的情况，而对远处的上级节点只了解大致情况。即每一物理节点保持聚合的网络影像(见例2)。

例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算法解决，时延约束多播路由问题也较容易解决。