路由

路由（routing）是任何网络中选取路径的程序，在此"程序"是指一组在电脑中执行的程式。电脑网络由称为节点的许多机器(例如电脑)以及连线至这些节点的路径或连结所组成。网络中相互连接的两个节点之间的通讯可以透过许多不同的路径进行。路由是使用一些预定规则选取最佳路径的程序。

设置与发展路由的原因是路由建立了网络通讯的效率。网络通讯失败会导致使用者载入网站页面需要长时间等待。因为无法处理大量使用者，它也可能会导致网站服务器失败。路由可以管理资料流量，来协助将网络故障降至最低，让网络尽可能使用其容量而不会产生拥塞。

其目的是通过互联的网络把信息从源地址以有效率的方式传输到目的地址的活动。路由发生在OSI网络参考模型中的第三层即网络层。

路由引导分组转送，经过一些中间的节点后，到它们最后的目的地。作成硬件的话，则称为路由器。路由通常根据路由表——一个储存到各个目的地的最佳路径的表——来引导分组转送。因此为了有效率的转送分组，建立储存在路由器内存内的路由表是非常重要的。

路由与桥接的不同，在于路由假设位址相似的节点距离相近。这使得路由表中的一项纪录可以表示到一群位址的路径。因此，在大型网络中，路由优于桥接，且路由已经成为互联网上寻找路径的最主要方法。

较小的网络通常可以手动设定路由表，但较大且拥有复杂拓扑的网络可能常常变化，若要手动建立路由表是不切实际的。尽管如此，大多数的公共交换电话网络（PSTN）仍然使用预先计算好的路由表，在直接连线的路径断线时才使用预备的路径；见公共交换电话网络由。“动态路由”尝试按照由路由协定所携带的资讯来自动建立路由表以解决这个问题，也让网络能够近自主地避免网络断线或失败。

动态路由目前主宰了整个互联网。然而，设定路由协定常须要经验与技术；目前的网络技术还没有发展到能够全自动地设定路由。

分组交换网络（例如互联网）将资料分割成许多带有完整目的地位址的分组，每个分组单独转送。而电路交换网络（例如公共交换电话网络）同样使用路由来找到一条路径，让接下来的资料能够抵达正确的目的地。

## 动态路由

若某个设定好的路径无法使用时，现存的节点必须决定另一个传送资料到目的地的路径。他们通常使用以下两种形式的路由协定来达成：距离向量算法与连线状态算法。所有路由算法几乎都可以分类到这两种算法中。

### 距离向量算法

距离向量算法使用Bellman-Ford算法。对于每一条网络上节点间的路径，算法指定一个“成本”给它们。节点会选择一条总成本（经过路径的所有成本总和）最低的路径，用来把资料从节点甲送到节点乙。

此算法非常的简单。当某节点初次启动时，将只知道它的邻居节点（直接连接到该节点的节点）与到该节点的成本。（这些资讯、目的地列表、每个目的地的总成本，以及到某个目的地所必须经过的“下一个节点”，构成路由表，或称距离表。）每个节点定时地将目前所知，到各个目的地的成本的资讯，送给每个邻居节点。邻居节点则检查这些资讯，并跟目前所知的资讯做比较；如果到某个目的地的成本比目前所知的低，则将收到的资讯加入自己的路由表。经过一段时间后，网络上的所有节点将会了解到所有目的地的最佳“下一个节点”与最低的总成本。

当某个节点断线时，每个将它当作某条路径的“下一个节点”的节点会将该路由资讯舍弃，再建立新的路由表资讯。接着，他们将这些资讯告诉所有相邻的节点，再找出到所有可抵达的目的地之新路径。

### 连线状态算法

在连线状态算法中，每个节点拥有网络的图谱（一个图）。每个节点将自己可以连接到的其他节点资讯传送到网络上所有的节点，而其他节点接着各自将这个资讯加入到图谱中。每个路由器即可根据这个图谱来决定从自己到其它节点的最佳路径。

完成这个动作的算法——Dijkstra算法——建立另一种资料结构——树。节点产生的树将自己视为根节点，且最后这棵树将会包含了网络中所有其他的节点。一开始，此树只有根节点（节点自己）。接着在树中已有的节点的邻居节点且不存在树中的节点集合中，选取一个成本最低的节点加入此树，直到所有节点都存入树中为止。

这棵树即用来建立路由表、提供最佳的“下一个节点”等，让节点能跟网络中其它节点通讯。

### 路由算法的比较

在小型网络中，距离向量路由协定十分简单且有效率，且只需要一些管理。然而，它们的规模性不好，且收敛性质也十分差，因此促进了较复杂但规模性较好的连线状态路由协定的开发，以使用在较大型的网络。距离向量路由协定也有无限计数问题。

连线状态路由协定的主要优点是在限制的时间内，对于连线改变（例如断线）的反应较快。而且连线状态路由协定在网络上所传送的封包也比距离向量路由协定的封包小。距离向量路由协定必须传送一个节点的整个路由表，但连线状态路由协定的封包只需要传输该节点的邻居节点资讯即可。因此，这些封包小到不会占用可观的网络资源。连线状态路由协定的主要缺点则是比距离向量路由协定需要较多的储存空间与较强的计算能力。

## 路由协定与可被绕送协定

有时路由协定与可被绕送协定常会令人混淆：

- 可被绕送协定：任何一个提供足够的网络层位址资讯让封包可被从一个装置转送到另一个，而不需要知道来源到目的地的整条路径的网络通讯协定。“可被绕送协定”定义了封包的格式与封包字段的使用方式。封包通常从一个终端系统被递送到另一个。IP是一个可被绕送协定，而以太网路是一个不可被绕送协定的例子。
- 路由协定：在网络间交换路由资讯，让路由器可动态建立路由表的通讯协定。传统的IP路由十分简单，因为它使用下一个节点路由方法，也就是路由器只需要考虑将封包送到哪一个“下一个节点”，而不需考虑到目的地的整条路径。

虽然动态路由可能非常复杂，但它使得互联网十分有弹性，且让互联网的规模自从采用IP以后成长了超过八个数量级。

路由度量（routing metric）包含了被路由算法使用来决定哪一条路径较另一条路径好的所有数值。度量可能包括许多资讯，例如带宽、延迟、经过节点数、路径成本、负载、MTU、可靠性及传输成本等。路由表只储存最佳的可能路径，但连线状态或拓扑数据库可能储存其他相关的资讯。

当路由器从不同的路由协定里发现有多个能抵达相同目的地的不同路径时，它们使用称为管理距离（administrative distance）的特性来选择最佳的路径。管理距离定义了路由协定的可靠程度。每个路由协定按照管理距离值，由最可靠到最不可靠排列来区分优先级。

依照路由器与其他自治系统的关系，有许多种类的路由协定：

- Ad hoc网络路由协定出现在没有或一点点基础的网络。参见Ad hoc路由协定列表以获得提议中的协定。
- 内部闸道协定（IGPs）在单一的自治系统中交换路由资讯。常见的范例包括：
- IGRP（Interior Gateway Routing Protocol）
- EIGRP（Enhanced Interior Gateway Routing Protocol）
- OSPF（Open Shortest Path First）
- RIP（Routing Information Protocol）
- IS-IS（Intermediate System to Intermediate System）
- 外部闸道协定（EGPs）在不同的自治系统中交换路由资讯。EGP包括：
- EGP（原本用来连接互联网骨干的外部闸道协定，现在已不再使用）
- BGP（Border Gateway Protocol：大约从1995年开始使用目前的版本，BGPv4）

## 参考资料

- Ciscopress ISBN 978-1-58705-202-6

## 外部链接

- Routing and Routed Protocols
- 路由 路由作业图
- Router Troubleshooting Primer 路由问题的除错步骤
- Count-To-Infinity Problem
- "Stability Features" 一种避免 Count-To-Infinity 问题的方法