何为路由

路由工作在TCP/IP四层协议栈的网络层，通过转发分组实现网络互连，并连接两个IP子网。是指分组从源端到目的端时路径的进程。在我国，路由一般支持TCP/IP协议。路由器根据网络层的地址和路由器内部维护的路由表决定下一跳地址，分组到达路由时，更改链路层MAC帧的报头继续转发。

　　平常人们一直容易将路由与桥接弄混，但是桥接和路由的区别非常明显：路由与桥接的关键区别点在于路由发生在网络层，桥接发生在链路层。

路由转发过程

路由转发过程：先确定最短路径，然后再通过所选路径上的网络传输数据。

　　一个分组到达路由器之后，先于本地路由表中的对应的子网掩码做按位与运算，然后再在本地的路由表中查询，如果与本地IP相同，则已经到达目的端，由当前路由解析数据；如果计算出不是本地IP地址，则此IP为下一跳的路由IP，继续进行路由转发；若在当前路由器中查询不到下一跳地址，即转向默认的下一跳IP。转发分组不可能在一个路由停下，这样会给当前路由的性能造成负担，且每个转发分组的IP数据包的报头中都有一个8位的生存时间TTL，这个生存时间并不是以时间单位计数，而是计算当前已经转发过的路由次数，在源端，设置好最大转发次数值，即生存时间，每经过一个路由，数值减一，直到最终路由器检查到生存时间为0。则丢弃该分组。

路由算法的区分要素

静态

严格意义上来说，静态算法并不能称之为算法。

　　是网络在开始运行前由网关建立的映射关系，在网关不更改的情况下，这种静态算法基本不会变，且设计也相对简单。但因为无法变化的原因，静态算法不能对网络关系的变化做出改变。所以在大型网络中并不适用。

动态

动态路由是在静态路由上发展出现的，当使用场景变大，网络服务存在变化，必须在某些用户不使用路由发送数据时，断开他的连接，给所需用户。且在最终不可分组路由时可以进行静态算法的补充。

路径算法

一些复杂的协议支持源端到目的端的多条路径，例如：源端A经路由B、路由C可以到达目的端E，A亦可以经路由D到达目的端E。此时，源端A到目的端E有两条路径可走，经过路径算法，将会选择一条最短、最高效、最快的路径。

　　本例中，若没有其他情况的话，路径算法将会选择A–D--E路径，但若是A–D路径发生拥塞，那么根据路径算法将会选择A–B--C–E路径。

平坦与分层

平坦路由工作在平坦的环境中，指的是每个路由之间的地位是平等的；在分层的路由系统中，各个路由网络犹如一个多叉树一般，存在主干路由，非主干路由上的数据由非主干路由流向主干路由，再由主干路由流向目的端所在的非主干路由。

　　例如：A是一个双亲节点，B和C是A的孩子节点，这里面，A、B、C都是路由，不同的是，A是主干路由，B、C是非主干路由，B的数据要往C发，路径为：B–A--C。

主机与路由器

一些路由算法中，因为源端路由功能的强大性，所以在源端发送数据时已经计算好源端数据的所有转发分组的路由路径。源端路由在探索过所有可以到达目的端的路径之后，根据算法，得到一个最佳路径。

　　主机智能系统通常能选择更佳的路径，因为在发送数据前，已经计算所有的路径而得到了一条最佳路径。

　　路由器智能则是每个路由均认为主机路由对路径一无所知，每个路由根据自己的算法将分组转发到下一个路由中。

链接与Bellman-Ford算法

链接算法将路由的路由表中已确定的、已连接的部分发给网络中的每个路由节点，则此网络中的每个路由都知道所有路由的路由信息。如此一来，根据算法得到最佳路径的速度快，得到的最佳路径也准确。

　　Bellaman-Ford算法则是将路由中路由表的全部信息发送给与他相连的邻居节点。

路由算法的衡量标准

因为路由算法多种多样，在何种情况下使用何种路由算法，则成了网络路由布置的重中之重，所以，路由的衡量标准必须最科学，最准确。

　　1、可靠性

　　路由算法计算得到的路径，在一段时间后可能失效，或者自身计算得到路径是一条不存在的路径，导致分组在网络中成为“流浪儿”。

　　2、路径长度

　　即分组在路由过程中转发的次数。

　　3、路由延迟

　　数据从源端发送，到目的端接收数据的所花时间。

　　4、负载

　　网络中路由器的繁忙程度。

　　5、通信代价

　　即通信花费的运作费，维护费等资金费用。

路径算法的代表算法

LS算法

在连接初，源端路由会向全网络中的各个路由发送一个分组数据包，每个路由则会回复给他一个分组数据包，其中包含自己的IP地址。

　　源端路由向全网络发送一个响应数据包，每个接收到的路由则会回复一个应答数组包，收到应答数据包后，将往返时间除以2，得到路由时间以及延时时间的总和。

　　向网络中公布自己的信息，同时接收其他路由发来的信息。，这样，每个路由都会及时更新自己的路由表等其他信息，维持自己的路由信息时最新的。

　　选择一个合适的算法，得到两个端的最佳路径。

　　由此看来，LS算法貌似是一个站在大局上对待网络上所有路由的架构的建立，而不针对的那个路由之间的转发分组。

Dijkstra算法

路由器先建立一张网络图，确定源端、目的端，然后建立一个邻接矩阵，每两个路由节点之间都有自己的链路权值，例如a，b节点的链路权值就是[i，j]，i和j分别是a路由和b路由的权值。

　　路由器为每个节点维护一个状态记录，包含三个字段：

　　1、前序字段–当前节点的前一节点；

　　2、长度字段–从源端到当前路由的权值之和；

　　3、标号字段–表示节点的状态–永久或暂时

　　然后路由器初始化所有节点的状态纪录，长度设置为无穷大，标号为暂时。

路由器将源端路由的标号设为“永久”，记为T节点，随即检查与标号为“永久”节点直接相连的路由节点，选择路径最近节点将其标号设为“永久”，此节点为最新的T节点。

　　检查当前T节点是否为目的端节点，如果不是，则继续上述操作，如果是，则根据回溯法记录经过的每一个节点，则为源端到目的端的路径。

链路算法及Bellman-Ford算法

本算法在之前已有提及，不作描述。