计算机网络中的两类路由算法

① internet中的路由算法的应用和发展

路由算法可以根据多个特性来加以区分。首先，算法设计者的特定目标影响了该路由协议的操作；其次，存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；最后，路由算法使用多种metric，影响到最佳路径的计算。
路由算法通常具有下列设计目标的一个或多个：

优化

简单、低耗

健壮、稳定

快速聚合

灵活性

优化指路由算法选择最佳路径的能力，根据metric的值和权值来计算。例如有一种路由算法可能使用跳数和延迟，但可能延迟的权值要大些。当然，路由协议必须严格定义计算metric的算法。

路由算法也可以设计得尽量简单。换句话说，路由协议必须高效地提供其功能，尽量减少软件和应用的开销。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。

路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。

此外，路由算法必须能快速聚合，聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。
各路由算法的区别点包括：

静态与动态

单路径与多路径

平坦与分层

主机智能与路由器智能

域内与域间

链接状态与距离向量

(1)静态与动态

静态路由算法很难算得上是算法，只不过是开始路由前由网管建立的表映射。这些映射自身并不改变，除非网管去改动。使用静态路由的算法较容易设计，在网络通信可预测及简单的网络中工作得很好。

由于静态路由系统不能对网络改变做出反映，通常被认为不适用于现在的大型、易变的网络。九十年代主要的路由算法都是动态路由算法，通过分析收到的路由更新信息来适应网络环境的改变。如果信息表示网络发生了变化，路由软件就重新计算路由并发出新的路由更新信息。这些信息渗入网络，促使路由器重新计算并对路由表做相应的改变。

动态路由算法可以在适当的地方以静态路由作为补充。例如，最后可选路由（router of last resort），作为所有不可路由分组的去路，保证了所有的数据至少有方法处理。

(2)单路径与多路径

一些复杂的路由协议支持到同一目的的多条路径。与单路径算法不同，这些多路径算法允许数据在多条线路上复用。多路径算法的优点很明显：它们可以提供更好的吞吐量和可靠性。

(3)平坦与分层
一些路由协议在平坦的空间里运作，其它的则有路由的层次。在平坦的路由系统中，每个路由器与其它所有路由器是对等的；在分层次的路由系统中，一些路由器构成了路由主干，数据从非主干路由器流向主干路由器，然后在主干上传输直到它们到达目标所在区域，在这里，它们从最后的主干路由器通过一个或多个非主干路由器到达终点。

路由系统通常设计有逻辑节点组，称为域、自治系统或区间。在分层的系统中，一些路由器可以与其它域中的路由器通信，其它的则只能与域内的路由器通信。在很大的网络中，可能还存在其它级别，最高级的路由器构成了路由主干。

分层路由的主要优点是它模拟了多数公司的结构，从而能很好地支持其通信。多数的网络通信发生在小组中（域）。因为域内路由器只需要知道本域内的其它路由器，它们的路由算法可以简化，根据所使用的路由算法，路由更新的通信量可以相应地减少。

(4)主机智能与路由器智能

一些路由算法假定源结点来决定整个路径，这通常称为源路由。在源路由系统中，路由器只作为存贮转发设备，无意识地把分组发向下一跳。其它路由算法假定主机对路径一无所知，在这些算法中，路由器基于自己的计算决定通过网络的路径。前一种系统中，主机具有决定路由的智能，后者则为路由器具有此能力。

主机智能和路由器智能的折衷实际是最佳路由与额外开销的平衡。主机智能系统通常能选择更佳的路径，因为它们在发送数据前探索了所有可能的路径，然后基于特定系统对“优化”的定义来选择最佳路径。然而确定所有路径的行为通常需要很多的探索通信量和很长的时间。

(5)域内与域间

一些路由算法只在域内工作，其它的则既在域内也在域间工作。这两种算法的本质是不同的。其遵循的理由是优化的域内路由算法没有必要也成为优化的域间路由算法。
(6)链接状态与距离向量

链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。距离向量算法（也叫做Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。

由于链接状态算法聚合得较快，它们相对于距离算法产生路由环的倾向较小。在另一方面，链接状态算法需要更多的CPU和内存资源，因此链接状态算法的实现和支持较昂贵。虽然有差异，这两种算法类型在多数环境中都可以工作得很好。

3、路由的metric

路由表中含有由交换软件用以选择最佳路径的信息。但是路由表是怎样建立的呢？它们包含信息的本质是什么？路由算法怎样根据这些信息决定哪条路径更好呢？

路由算法使用了许多不同的metric以确定最佳路径。复杂的路由算法可以基于多个metric选择路由，并把它们结合成一个复合的metric。常用的metric如下：

路径长度

可靠性

延迟

带宽

负载

通信代价

路径长度是最常用的路由metric。一些路由协议允许网管给每个网络链接人工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。其它路由协议定义了跳数，即分组在从源到目的的路途中必须经过的网络产品，如路由器的个数。

可靠性，在路由算法中指网络链接的可依赖性（通常以位误率描述），有些网络链接可能比其它的失效更多，网路失效后，一些网络链接可能比其它的更易或更快修复。任何可靠性因素都可以在给可靠率赋值时计算在内，通常是由网管给网络链接赋以metric值。

路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延迟，包括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间网络链接的拥塞程度以及物理距离。因为延迟是多个重要变量的混合体，它是个比较常用且有效的metric。

http://tech.ddvip.com/2007-10/119152495935811.html
这里面有解释。。恩

② 路由算法的简介

路由算法是提高路由协议功能，尽量减少路由时所带来开销的算法。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。
此外路由算法必须能快速聚合，聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。

③ 计算机网络-4-6-互联网的路由选择协议

路由选择协议的核心是 路由算法 。即 需要一种算法来获取路表中的各项 ，一个比较好的路由选择算法应该有以下特点[BELL86]:

一个实际的路由选择算法，应该尽可能的接近于理想的算法，在不同的应用条件下，可以对上面提出的六个方面有不同的侧重。

倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分，则只有两大类： 静态路由选择策略 和 动态路由选择策略 。静态路由选择策略也叫做 非自适应路由选择 ，其特点是简单和开销较小，但不能即使适应网络状态的变化。对于很简单的小网络，完全可以采用静态路由选择，用人工配置每一条路由。动态路由选择也叫做 自适应路由选择 ，其特点是能够较好的适应网络状态的变化，但实现起来较为复杂，开销也比较大，因此动态路由选择适用于较复杂的大网络。

互联网采用的路由选择协议主要是自适应的(动态的)，分布式路由选择协议。由于以下两种原因，互联网采用分层次的路由选择协议：

为此，可以把整个互联网划分为许多较小的 自治系统AS(autonomous system) ,自治系统AS是在单一技术管理下的一组路由器，而这些路由器使用一种自治系统内部的路由选择协议和共同的度量，一个AS对其他AS表现的出是 一个单一的和一致的路由选择策略 。

在目前的互联网中，一个大的ISP就是一个自治系统。这样，互联网就把路由选择协议划分为两大类：

自治系统之间的路由选择协议也叫做 域间路由选择(interdomain routing) ，而在自治系统内部的路由选择叫做 域内路由选择(intradomain routing) 。如图4-31

RIP（routing information protocol）是内部网关协议IGP中最先得到广泛使用的协议[RFC1058],也叫 路由信息协议 ，RIP是一种分布式的 基于距离向量的路由选择协议 。最大的优点就是简单。

RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录（因此这是一组距离，叫做距离向量），RIP将距离定义如下：

从一路由器到直接连接的网络的距离为1，从路由器到非之间的网络的距离定义为所经过的路由器数+1。

RIP协议的距离也称之为 跳数 ，但是一条跳数最多只能包含15个路由器，因此，当距离=16时，就相当于不可达。因此RIP只能适用于小型互联网。

注意的是，到直接连接的网络也定义为0(采用这种定义的理由是：路由器在和直接连接在该网络上的主机进行通信并不需要经过另外的路由器，既然经过每一个路由器都要将距离增加1，那么不经过路由器就不需要+1，就是0)。

RIP不能在两个网络之间同时使用多条路由。RIP选择一条具有最少路由器的路由（最短路由），哪怕还存在另一条高速低延时的但是路由器较多的路由。

路由器在刚开始工作的时候，其内部路由表是空的。然后路由器就可以和直接相连的几个网络的距离(这些距离为1)，接着，每个路由器和与自己相连的路由器不断交换路由表信息，经过若干次更新后，所有的路由器最终就可以知道本自治系统中任何一个网络地址和最短下一跳路由器的地址。

路由器最主要的信息是：到某个网路的距离（最短距离），以及下一跳的地址，路由表更新的原则是找出到每个网络的 最短距离 ，这种算法又称之为 距离向量算法 。

对 每一个相邻的路由器 发送过来的RIP报文，进行以下步骤：

算法描述：其实就是求一个路由器到另一个路由器的最短距离。

例题：
已知路由器R6有表4-9(a)所表示的路由表，现在收到相邻路由器路由表R4发过来的路由更新信息，如图4-9(b)所示。试更新路由器R6的路由表。

解：首先把R4发过来的路由表中的距离都+1：

把这个表和R6的路由表进行比较：

RIP协议让每一个自治系统中的所有路由都和自己的相邻路由器定期交换路由表信息，并不断更新路由表，使得每从 每一个路由器到每一个目的网络的路由都是最短距离（也就是跳数最小）。

现在比较新的RIP协议报文格式是1998年提出的RIP2。

RIP协议使用运输层的用户数据报（UDP端口为520）进行传输。

RIP报文由首部和路由部分组成。
RIP首部占4个字节，其中的命令字段指出报文的意义。

RIP2报文中的路由部分有若干路由信息组成，每个路由信息需要用20字节。 地址标识符(又称地址列别) 字段用来标识所用的地址协议。如果采用IP地址就为2。 路由标记填入自治系统号ASN（Autonomous System Number） ，这是考虑使用RIP有可能收到本自治系统以外的路由选择信息，再后面指出某个 网络地址 ， 下一跳路由器地址 以及 到此网络的距离 ，一个RIP报文最多可以包含25个路由，因而RIP报文的最大长度是4+20x25=504字节。如果超过，则必然再使用以恶搞RIP报文来传送。

RIP还具有简单的鉴别功能，若使用鉴别功能，则将原来写入第一个路由信息(20字节)的位置用作鉴别，这时应该将地址标识符置为全1(0xFFFF),而路由标记写入鉴别类别，剩下的16字节作为鉴别数据，在鉴别数据之后才能写入路由信息，但这时只能写入24个路由信息。

RIP存在的一个问题是 当网络出现故障的时候，要经过比较长的时间才能将信息传送到所有的路由器 ，RIP协议的这一特点是： 好消息传播的很快，而坏消息传播的很慢 ，网络出现故障的传播时间往往需要经过较长时间，这是RIP协议的一个主要缺点。

为了使坏消息传播的更快些，可以采用多种措施，例如，让路由器记录收到某特定路由信息的接口，而不是让同一个路由信息再通过此接口反方向传送。

总之，RIP协议最大的优点是 实现简单，开销较小 ，但RIP协议缺点也很明显，首先 限制了网络规模，因为路由器最大的跳数是15跳，一般中大型网络规模RIP协议就不适用了 。其次就是 路由器之间交换的路由信息是路由器中完整的路由表，因而随着网络规模变大，开销也就增加 。最后就是 好消息传播的很快，坏消息传播的很慢 。

④ 《计算机网络-自顶向下方法》第四章-网络层 要点

网络层的作用：实现主机到主机的通信服务，将分组从一台发送主机移动到一台接收主机。

1、转发涉及分组在单一的路由器中从一条入链路到一条出链路的传送。
2、路由选择涉及一个网络的所有路由器，它们经路由选择协议共同交互，以决定分组从源到目的地结点所采用的路径。计算这些路径的算法称为路由选择算法。

每台路由器都有一张转发表，路由器通过检查到达分组首部字段的值来转发分组，然后使用该值在该路由器的转发表中索引查找。路由选择算法决定了插入路由器转发表中的值。

路由选择算法可能是集中式的，或者是分布式的。但在这两种情况下，都是路由器接收路由选择协议报文，该信息被用于配置其转发表。

网络层也能在两台主机之间提供无连接服务或连接服务。同在运输层的面向连接服务和无连接服务类似，连接服务需要握手步骤，无连接服务不需要握手。但它们之间也有差异：
1、 在网络层中，这些服务是由网络层向运输层提供的主机到主机的服务。在运输层中，这些服务则是运输层向应用层提供的进程到进程的服务。
2、 在网络层提供无连接服务的计算机网络称为数据报网络；在网络层提供连接服务的计算机网络称为虚电路网络。
3、 在运输层实现面向连接的服务与在网络层实现连接服务是根本不同的。运输层面向连接服务是在位于网络边缘的端系统中实现的；网络层连接服务除了在端系统中，也在位于网络核心的路由器中实现。（原因很简单：端系统和路由器都有网络层）

虚电路网络和数据报网络是计算机网络的两种基本类型。在作出转发决定时，它们使用了非常不同的信息。

IP地址有32比特，如果路由器转发表采用“蛮力实现”将对每个可能的目的地址有一个表项。因为有超过40亿个可能的地址，这种选择完全不可能（即使用二分查找也十分慢）。
我们转发表的表项可以设计为几个表项，每个表项匹配一定范围的目的地址，比如有四个表项

（你可能也会考虑到，IP地址有32比特，如果每个路由器设计为只有2个表项，那么也只需要有32个路由器就可以唯一确定这40亿个地址中的一个。）

最长前缀匹配规则，是在转发表中寻找最长的匹配项，并向与最长前缀匹配相关联的链路接口转发分组。这种规则是为了与因特网的编址规则相适应。

1、输入端口
“使用转发表查找输出端口”是输入端口最重要的操作（当然还有其他一些操作）。输入端口执行完这些所需的操作后，就把该分组发送进入交换结构。如果来自其他输入端口的分组当前正在使用交换结构，一个分组可能会在进入交换结构时被暂时阻塞，在输入端口处排队，并等待稍后被及时调度以通过交换结构。
2、交换结构
交换结构的三种实现方式

3、输出端口
分组调度程序 处理在输出端口中排队的分组
4、路由选择处理器

</br>

</br>

IP协议版本4，简称为IPv4；IP协议版本6，简称为IPv6。

如上图所示，网络层有三个主要的组件
1、IP协议
2、路由选择协议
3、ICMP协议 (Internet Control Message Protocol, 因特网控制报文协议)

</br>

不是所有链路层协议都能承载相同长度的网络层分组。有的协议能承载大数据报，而有的协议只能承载小分组。例如，以太网帧能够承载不超过1500字节的数据，而某些广域网链路的帧可承载不超过576字节的数据。

一个链路层帧能承载的最大数据量叫做最大传送单元(Maximun Transmission Unit, MTU)

所以链路层协议的MTU严格限制着IP数据报的长度。这也还不是主要的问题，问题在于发送方与目的地路径上的每段链路可能使用不同的链路层协议，且每种协议可能具有不同的MTU。

举个例子：假定从某条链路收到一个IP数据报，通过检查转发表确定出链路，并且该出链路的MTU比该IP数据报的长度要小。那么如何将这个过大的IP分组压缩进链路层帧的有效载荷字段呢？

解决办法是，将IP数据报中的数据分片成两个或更多个较小的IP数据报，用单独的链路层帧封装这些较小的IP数据报；然后向输出链路上发送这些帧。每个这些较小的数据报都被称为片(fragment)。

路由器完成分片任务。同时，为了使得网络内核保持简单，IPv4设计者把数据报的重组工作放到端系统中，而非放到网络路由器中。

前提：一个4000字节的数据报(20字节IP首部加上3980字节IP有效载荷)到达一台路由器，且必须被转发到一条MTU为1500字节的链路上。假定初始数据报贴上的标识号为777。

这意味着初始数据报中3980字节数据必须被分配到3个独立的片(其中的每个片也是一个IP数据报)

IP分片：

IP地址有32比特，分为网络号和主机号。
IP地址的网络部分（即网络号）被限制为长度为8、16或24比特，这是一种称为分类编址的编址方案。具有8、16和24比特子网地址的子网分别被称为A、B和C类网络。

但是它在支持数量迅速增加的具有小规模或中等规模子网的组织方面出现了问题。一个C类(/24)子网仅能容纳多大2^8 - 2 = 254台主机(2^8 = 256, 其中的两个地址预留用于特殊用途)，这对许多组织来说太小了。然而一个B类(/16)子网可支持多达65534台主机，又太大了。这导致B类地址空间的迅速损耗以及所分配的地址空间的利用率低。

广播地址255.255.255.255。当一台主机发出一个目的地址为255.255.255.255的数据报时，该报文会交付给同一个网络中的所有主机。

某组织一旦获得了一块地址，它就可以为本组织内的主机与路由器接口逐个分配IP地址。既可手工配置IP地址，也可以使用动态主机配置协议(Dynamic Host Configuration Protocol, DHCP)自动配置。DHCP还允许一台主机得知其他信息，如它的子网掩码、它的第一跳路由器地址(常称为默认网关)与它的本地DNS服务器的地址。

由于DHCP具有能将主机连接进一个网络相关方面的自动能力，它又被称为即插即用协议。

DHCP是客户-服务器协议。客户通常是新达到的主机，它要活的包括自身使用的IP地址在内的网络配置信息。在最简单的场合下，每个子网将具有一台DHCP服务器。如果在某子网中没有服务器，则需要一个DHCP中继代理(通常是一台路由器)，这个代理知道用于该网络的DHCP服务器的地址。

DHCP协议工作的4个步骤：

网络地址转换(Network Address Translation, NAT)

ICMP通常被认为是IP的一部分，但从体系结构上将它是位于IP之上的，因为ICMP报文是承载在IP分组中的。即ICMP报文是作为IP有效载荷承载的，就像TCP与UDP报文段作为IP有效载荷被承载那样。

众所周知的ping程序发送一个ICMP类型8编码0的报文到指定主机。看到该回显请求，目的主机发回一个类型0编码0的ICMP回显回答。大多数TCP/IP实现直接在操作系统中支持ping服务器，即该服务器不是一个进程。

新型IPv6系统可做成向后兼容，即能发送、路由和接收IPv4数据报，要使得已部署的IPv4系统能够处理IPv6数据报，最直接的方式是采用一种双栈方法。

1、链路状态(Link State, LS)算法：属于全局式路由选择算法，这种算法必须知道网络中每条链路的费用。费用可理解为链路的物理长度、链路速度，或与该链路相关的金融上的费用。链路状态算法采用的是Dijkstra算法。

2、距离向量(Distance-Vector, DV)算法：属于迭代的、异步的和分布式的路由选择算法。
“迭代的”，是因为此过程一直要持续到邻居之间无更多信息要交换为止。
“异步的”，是因为它不要求所有结点相互之间步伐一致地操作。
“分布式的”，是因为每个结点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。
DV算法的方程：

其中，dx(y)表示从结点x到结点y的最低费用路径的费用，c(x, v)是结点x到结点v的费用，结点v指的是所有x的相连结点，所以x的所有相连结点都会用minv方程计算。

（N是结点（路由器）的集合，E是边（链路）的集合）

为了减少公共因特网的路由选择计算的复杂性以及方便企业管理网络，我们将路由器组织进自治系统。

在相同AS中的路由器全都运行同样的路由选择算法，且拥有彼此的信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议。

当然，将AS彼此互联是必需的，因此在一个AS内的一台或多台路由器将有另外的任务，即负责向在本AS之外的目的地转发分组。这些路由器被称为网关路由器。

分为自治系统内部的路由选择和自治系统间的路由选择

1、因特网中自治系统内部的路由选择：路由选择信息协议(Routing Information Protocol, RIP)
2、因特网中自治系统内部的路由选择：开放最短路优先(Open Shortest Path First, OSPF)
3、自治系统间的路由选择：边界网关协议(Broder Gateway Protocol, BGP)

为什么要使用不同的AS间和AS内部路由选择协议？

实现广播的方法
1、无控制洪泛。该方法要求源结点向它的所有邻居发送分组的副本。当某结点接收了一个广播分组时，它复制该分组并向它的所有邻居（除了从其接收该分组的那个邻居）转发之。
致命缺点： 广播风暴 ，如果图具有圈，那么每个广播分组的一个或多个分组副本将无休止地循环。
2、受控洪泛。用于避免广播风暴，关键在于正确选择何时洪泛分组，何时不洪泛分组。受控洪泛有两种方法：序号控制洪泛、反向路径转发(Reverse Path Forwarding, RPF)
3、生成树广播。虽然序号控制洪泛和RPF能避免广播风暴，但是它们不能完全避免冗余广播分组的传输。

多播：将分组从一个或多个发送方交付到一组接收方

每台主机有一个唯一的IP单播地址，该单播地址完全独立于它所参与的多播组的地址。

因特网网络层多播由两个互补组件组成：因特网组管理协议(Internet Group Management Protocol, IGMP)和多播路由选择协议

IGMP只有三种报文类型：membership_query报文，membership_report报文，leave_group报文。

与ICMP类似，IGMP报文也是承载在一个IP数据报中。

因特网中使用的多播路由选择
1、距离向量多播路由选择协议
2、协议无关的多播路由选择协议

⑤ 计算机网络路由算法

关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：
总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。

⑥ 计算机网络 路由选择

路由算法分为:静态路由算法跟动态路由算法(又称为 自适应路由选择算法)
静态算法分为:泛射路由算法(扩散法) 固定路由算法
动态路由算法分为: 距离矢量路由算法 链路状态路由算法

动态路由算法,能够比较好的适应网络流量,拓扑结构的变化,有利于改善网络的性能,但是由于算法比较复杂,会增加网络的负担,开销比较大~!

最常见的动态路由算法有两种其算法是:
距离矢量算法.每个路由器维护一张路由表(既一个矢量),他以子网中的没个路由器为索引,表中给出了当前已知的路由器到每个目标路由器的最佳距离,以及所使用的线路.通过在邻居之间相互交换信息,路由器不断更新他们的内部路由表. 一个路由器针对每个邻居都执行一个距离加法计算,就可以发现最佳的到达目标路由器的估计值,然后在新的路由表中使用这个最佳估计值以及对应的线路.

链路状态路由算法.
1: 发现自己的邻居.在每条线路上发送一个HELLO分组,另一端的路由器即返回一个应答来说明自己是谁~
2: 测量线路开销.在线路上发送一个ECHO分组,另一端回送一个应答,算出往返时间,除2就得到合理的估计值.
3: 创建链路状态分组.该分组内容首先是发送方的标示,接着是一个序列号(Seq)和年龄(Age),以及一个邻居列表.对于每个邻居也都要给出这个路由器到每个邻居的延迟.
4: 发布链路状态分组.首先使用泛射法发布链路状态分组,为了控制泛射过程,每个分组都宝号一个序列号,序列号随着每一个新的分组递增.每个路由器纪录下他所看到的分组列表中检查这个新进来的分组,如果是一个重复分组则丢弃,.如果一个分组的序列号小于当前所看到过的来自该路由器的最大序列号,则将它看着过时分组拒绝,因为该路由器已经有了更新的数据.
5: 计算新路由.一旦一个路由器已经获得了全部的链路状态分组后,它就可以构造出完整的子网图了.以为每条链路都已经被表示出来了.然后在路由器本地运行寻找最短路径算法,将该算法得出的结果安装在路由表里,然后恢复正常的操作.

⑦ 2、路由选择算法主要分哪几类分布式自适应算法的基本思想是什么

路由选择算法主要分两类：静态路由选择算法和动态路由选择算法
分布自适应路由选择算法的网络，所有节点定其地与其每个相邻节点交换路由选择信息。每个节点均存储一张以网络中其它每个节点为索引的路由选择表，网络中每个节点占用表中一项，每一项又分为两个部分，即所希望使用的到目的节点的输出线路和估计到目的节点所需要的延迟或距离。度量标准可以是毫秒或链路段数、等待的分组数、剩余的线路和容量等。对于延迟，节点可以直接发送一个特殊的称作“回声”（echo）的分组，接收该分组的节点将其加上时间标记后尽快送回，这样便可测出延迟。有了以上信息，节点可由此确定路由选择。

⑧ 路由算法主要有哪几种

静态路由算法主要有：
洪泛法（Flooding）
随机走动法（Random Walk）
最短路径法（Shortest Path，SP）
基于流量的路由算法(Flow-based Routing，FR)</ol>动态路由算法主要有：
距离矢量算法（RIP）
链路状态算法（OSPF）
平衡混合算法（EIGRP）</ol>

⑨ 路由的全方面讲解

路由是把信息从源穿过网络传递到目的的行为，在路上，至少遇到一个中间节点。路由通常与桥接来对比，在粗心的人看来，它们似乎完成的是同样的事。它们的主要区别在于桥接发生在OSI参考协议的第二层（链接层），而路由发生在第三层（网络层）。这一区别使二者在传递信息的过程中使用不同的信息，从而以不同的方式来完成其任务。

路由的话题早已在计算机界出现，但直到八十年代中期才获得商业成功，这一时间延迟的主要原因是七十年代的网络很简单，后来大型的网络才较为普遍。

二、路由的组成

路由包含两个基本的动作：确定最佳路径和通过网络传输信息。在路由的过程中，后者也称为（数据）交换。交换相对来说比较简单，而选择路径很复杂。

1、路径选择

metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。为了帮助选路，路由算法初始化并维护包含路径信息的路由表，路径信息根据使用的路由算法不同而不同。

路由算法根据许多信息来填充路由表。目的/下一跳地址对告知路由器到达该目的最佳方式是把分组发送给代表“下一跳”的路由器，当路由器收到一个分组，它就检查其目标地址，尝试将此地址与其“下一跳”相联系。下表为一个目的/下一跳路由表的例子。

表5-1 目的/下一跳对应表决定数据的最佳路径

http://www.linkwan.com/gb/routertech/netsys/images/route1.gif
路由表还可以包括其它信息。路由表比较metric以确定最佳路径，这些metric根据所用的路由算法而不同，下面将介绍常见的metric。路由器彼此通信，通过交换路由信息维护其路由表，路由更新信息通常包含全部或部分路由表，通过分析来自其它路由器的路由更新信息，该路由器可以建立网络拓扑细图。路由器间发送的另一个信息例子是链接状态广播信息，它通知其它路由器发送者的链接状态，链接信息用于建立完整的拓扑图，使路由器可以确定最佳路径。

2、交换

交换算法相对而言较简单，对大多数路由协议而言是相同的，多数情况下，某主机决定向另一个主机发送数据，通过某些方法获得路由器的地址后，源主机发送指向该路由器的物理（MAC）地址的数据包，其协议地址是指向目的主机的。

路由器查看了数据包的目的协议地址后，确定是否知道如何转发该包，如果路由器不知道如何转发，通常就将之丢弃。如果路由器知道如何转发，就把目的物理地址变成下一跳的物理地址并向之发送。下一跳可能就是最终的目的主机，如果不是，通常为另一个路由器，它将执行同样的步骤。当分组在网络中流动时，它的物理地址在改变，但其协议地址始终不变，如下图所示。

http://www.linkwan.com/gb/routertech/netsys/images/route2.gif
上面描述了源系统与目的系统间的交换，ISO定义了用于描述此过程的分层的术语。在该术语中，没有转发分组能力的网络设备称为端系统（ES--end system），有此能力的称为中介系统（IS--intermediate system）。IS又进一步分成可在路由域内通信的域内IS（intradomain IS）和既可在路由域内有可在域间通信的域间IS（interdomain IS）。路由域通常被认为是统一管理下的一部分网络，遵守特定的一组管理规则，也称为自治系统（autonomous system）。在某些协议中，路由域可以分为路由区间，但是域内路由协议仍可用于在区间内和区间之间交换数据。

三、路由算法

路由算法可以根据多个特性来加以区分。首先，算法设计者的特定目标影响了该路由协议的操作；其次，存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；最后，路由算法使用多种metric，影响到最佳路径的计算。下面的章节分析了这些路由算法的特性。

1、设计目标

路由算法通常具有下列设计目标的一个或多个：

优化

简单、低耗

健壮、稳定

快速聚合

灵活性

优化指路由算法选择最佳路径的能力，根据metric的值和权值来计算。例如有一种路由算法可能使用跳数和延迟，但可能延迟的权值要大些。当然，路由协议必须严格定义计算metric的算法。

路由算法也可以设计得尽量简单。换句话说，路由协议必须高效地提供其功能，尽量减少软件和应用的开销。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。

路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。

此外，路由算法必须能快速聚合，聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。

在下图中的路由环中，某分组在时间t1到达路由器1，路由器1已经更新并知道到达目的的最佳路径是以路由器2为下一跳，于是就把该分组转发给路由器2。但是路由器2还没有更新，它认为最佳的下一跳是路由器1，于是把该分组发回给路由器1，结果分组在两个路由器间来回传递直到路由器2收到路由更新信息或分组超过了生存期。

http://www.linkwan.com/gb/routertech/netsys/images/route3.gif
路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网络环境。例如，假定某网段断掉了，当知道问题后，很多路由算法对通常使用该网段的路径将迅速选择次佳的路径。路由算法可以设计得可适应网络带宽、路由器队列大小和网络延迟。

2、算法类型

各路由算法的区别点包括：

静态与动态

单路径与多路径

平坦与分层

主机智能与路由器智能

域内与域间

链接状态与距离向量

(1)静态与动态

静态路由算法很难算得上是算法，只不过是开始路由前由网管建立的表映射。这些映射自身并不改变，除非网管去改动。使用静态路由的算法较容易设计，在网络通信可预测及简单的网络中工作得很好。

由于静态路由系统不能对网络改变做出反映，通常被认为不适用于现在的大型、易变的网络。九十年代主要的路由算法都是动态路由算法，通过分析收到的路由更新信息来适应网络环境的改变。如果信息表示网络发生了变化，路由软件就重新计算路由并发出新的路由更新信息。这些信息渗入网络，促使路由器重新计算并对路由表做相应的改变。

动态路由算法可以在适当的地方以静态路由作为补充。例如，最后可选路由（router of last resort），作为所有不可路由分组的去路，保证了所有的数据至少有方法处理。

(2)单路径与多路径

一些复杂的路由协议支持到同一目的的多条路径。与单路径算法不同，这些多路径算法允许数据在多条线路上复用。多路径算法的优点很明显：它们可以提供更好的吞吐量和可靠性。

(3)平坦与分层

一些路由协议在平坦的空间里运作，其它的则有路由的层次。在平坦的路由系统中，每个路由器与其它所有路由器是对等的；在分层次的路由系统中，一些路由器构成了路由主干，数据从非主干路由器流向主干路由器，然后在主干上传输直到它们到达目标所在区域，在这里，它们从最后的主干路由器通过一个或多个非主干路由器到达终点。

路由系统通常设计有逻辑节点组，称为域、自治系统或区间。在分层的系统中，一些路由器可以与其它域中的路由器通信，其它的则只能与域内的路由器通信。在很大的网络中，可能还存在其它级别，最高级的路由器构成了路由主干。

分层路由的主要优点是它模拟了多数公司的结构，从而能很好地支持其通信。多数的网络通信发生在小组中（域）。因为域内路由器只需要知道本域内的其它路由器，它们的路由算法可以简化，根据所使用的路由算法，路由更新的通信量可以相应地减少。

(4)主机智能与路由器智能

一些路由算法假定源结点来决定整个路径，这通常称为源路由。在源路由系统中，路由器只作为存贮转发设备，无意识地把分组发向下一跳。其它路由算法假定主机对路径一无所知，在这些算法中，路由器基于自己的计算决定通过网络的路径。前一种系统中，主机具有决定路由的智能，后者则为路由器具有此能力。

主机智能和路由器智能的折衷实际是最佳路由与额外开销的平衡。主机智能系统通常能选择更佳的路径，因为它们在发送数据前探索了所有可能的路径，然后基于特定系统对“优化”的定义来选择最佳路径。然而确定所有路径的行为通常需要很多的探索通信量和很长的时间。

(5)域内与域间

一些路由算法只在域内工作，其它的则既在域内也在域间工作。这两种算法的本质是不同的。其遵循的理由是优化的域内路由算法没有必要也成为优化的域间路由算法。

(6)链接状态与距离向量

链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。距离向量算法（也叫做Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。

由于链接状态算法聚合得较快，它们相对于距离算法产生路由环的倾向较小。在另一方面，链接状态算法需要更多的CPU和内存资源，因此链接状态算法的实现和支持较昂贵。虽然有差异，这两种算法类型在多数环境中都可以工作得很好。

3、路由的metric

路由表中含有由交换软件用以选择最佳路径的信息。但是路由表是怎样建立的呢？它们包含信息的本质是什么？路由算法怎样根据这些信息决定哪条路径更好呢？

路由算法使用了许多不同的metric以确定最佳路径。复杂的路由算法可以基于多个metric选择路由，并把它们结合成一个复合的metric。常用的metric如下：

路径长度

可靠性

延迟

带宽

负载

通信代价

路径长度是最常用的路由metric。一些路由协议允许网管给每个网络链接人工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。其它路由协议定义了跳数，即分组在从源到目的的路途中必须经过的网络产品，如路由器的个数。

可靠性，在路由算法中指网络链接的可依赖性（通常以位误率描述），有些网络链接可能比其它的失效更多，网路失效后，一些网络链接可能比其它的更易或更快修复。任何可靠性因素都可以在给可靠率赋值时计算在内，通常是由网管给网络链接赋以metric值。

路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延迟，包括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间网络链接的拥塞程度以及物理距离。因为延迟是多个重要变量的混合体，它是个比较常用且有效的metric。

带宽指链接可用的流通容量。在其它所有条件都相等时，10Mbps的以太网链接比64kbps的专线更可取。虽然带宽是链接可获得的最大吞吐量，但是通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好。例如，如果一条快速链路很忙，分组到达目的所花时间可能要更长。

负载指网络资源，如路由器的繁忙程度。负载可以用很多方面计算，包括CPU使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资源的。

通信代价是另一种重要的metric，尤其是有一些公司可能关系运作费用甚于性能。即使线路延迟可能较长，他们也宁愿通过自己的线路发送数据而不采用昂贵的公用线路。

路由器的工作原理是什么？
路由器利用网络寻址功能使路由器能够在网络中确定一条最佳的路径 IP 地址的网络部
分确定分组的目标网络，并通过 IP地址的主机部分和设备的 MAC 地址确定到目标节点的连接
路由器的某一个接口接收到一个数据包时，会查看包中的目标网络地址以判断该包的目的地址在当前
的路由表中是否存在（即路由器是否知道到达目标网络的路径），如果发现包的目标地址与本路由器的某
个接口所连接的网络地址相同，那么马上数据转发到相应接口；如果发现包的目标地址不是自己的直连
网段，路由器会查看自己的路由表，查找包的目的网络所对应的接口，并从相应的接口转发出去如果路
由表中记录的网络地址与包的目标地址不匹配，则根据路由器配置转发到默认接口，在没有配置默认接口
的情况下会给用户返回目标地址不可达的 ICMP 信息

路由器包含了什么功能？
路由器包含了路由选择和交换的功能
路由器接口通常一个数据分组从一条数据链路传送到另一条数据链路
路由选择功能：为传送分组，路由器会使用地址的网络部分进行路由选择以确定一条最佳路径
路由交换功能：使路由器有能力接收分组并进行转发
所以路由是跨越

路由器在工作中要经历哪几个过程？
路由发现：学习路由的过程，动态路由通常由路由器自己完成，静态路由需要手工配置
路由转发：路由学习之后会照学习更新的路由表进行数据转发
路由维护：路由器通过定期与网络中其他路由器进行通信来了解网络拓扑变化以便更新路由表
路由器记录了接口所直连的网络 ID，称为直连路由，路由器可以自动学习到直连路由而不需要配置
路由器所识别的逻辑地址的协议必须被路由器所支持

路由有哪几种类型？各种路由的特点是什么？
路由分为静态路由
静态路由是由管理员在路由器进行手工配置的固定的路由
静态路由允许对路由的行为进行精确的控制减少了网络流量单向以及配置简单静态路由通常情
况下优先级最高，因为其管理距离最短
静态路由的配置方法：
Router（config）#ip route network [mask] {address | interface} [distance] [permantet]
目标网络 掩码 到达目标网络的下一个路由器地址或本地接口
默认路由是静态路由的一种，是指当路由表中与包的目标地址之间没有匹配的表项时路由器能够作出
的选择
Router（config）#ip route 0.0.0.0 0.0.0.0 下一个路由器的接口地址
Router（config）#ip classless
其中 0.0.0.0 0.0.0.0 代表将发往任何网络的包都转发到下一个路由器接口地址
Ip classless 指路由器接收到不能转发的包的时候会将其匹配给默认路由
并且返回目标地址不可达的 ICMP的消息
动态路由是网络中的路由器之间根据实时网络拓扑变化，相互通信传递路由信息，利用收到的路由信
息通过路由选择协议计算，更新路由表的过程
动态路由减少了管理任务
常见的动态路由包括距离矢量路由选择协议和链路状态路由选择协议