路由交换 算法？

一、路由交换 算法？

RIP（Routing information Protocol）是早期第一代动态路由协议，是一种基于距离矢量（Distance-Vector）算法来计算到达目的网络的最佳路径路由协议，它通过UDP报文进行路由信息的交换，使用的端口号为520，RIP是基于跳数（最多支持15跳）来衡量到达目的地址的距离，称为度量值，RIP协议有多个版本，分为v1/v2/ng版。

二、什么是标准路由算法？

路由选择算法在网络路由器中运行、交换和计算信息，用这些信息配置转发表。主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器,又称为该主机的第一跳路由器。每当主机发送一个分组时，该分组被传送给它的默认路由器。将源主机的默认路由器称作源路由器，把目的主机的默认路由器称作目的路由器。一个分组从源主机到目的主机的路由选择问题显然可归结为从源路由器到目的路由器的路由选择问题。

路由选择算法的目的是简单的，给定一组路由器以及连接路由器的链路，路由选择算法要找到一条从源路由器到目的路由器的"好"路径。通常，一条好路径指具有最低费用的路径。

三、时序数据库常用的算法？

基本： 线性表，链表，栈，队列 排序： 快速排序，堆排序，归并排序，希尔排序，插入排序，选择排序 二叉树： 前序，中序，后序遍历，层次遍历，包括递归算法和非递归算法两种 AVL树，Huffman编码 二叉树和树，森林之间的转换，穿线树 图算法： 深度优先遍历算法，广度优先遍历算法，最小生成树，最短路径 字符串： 查找子串，KMP算法 以上都是比较基本的算法，一定要弄懂

四、ospf协议使用什么路由算法？

OSPF协议使用的路由计算的算法是Dijkstra算法。

算法描述如下：

第一步：把Root加入最小树，并设Root可直达的顶点为候选人。

第二步：若候选人列表为空，则最小树生成，否则候选人列表中选取花费最小的，加入到最小树中。

第三步：把新加入的顶点所能直达的顶点列为候选人。

第四步：在候选人名单中除去最小树中已经出现的，返回到第二步。

工作过程：

通过LSDB可得到个顶点的连接状态，利用Dijkstra算法有"内"向外，从区域内到区域间，从AS内到AS外，诼步生成最小树，进而生成路由表。

五、路由算法六大准则？

选择路径的算法以及算法所使用的数据结构是网络层设计的最主要的内容。.

路由算法（routing algorithm）负责确定一个进来的分组应该被传送到哪一条输出线路上。若是数据报，则须对每个分组重新选择路径，而对于虚电路，分组只要沿着已经建立的路径向前传递即可（此时也称为会话路由）。

静态路由算法：非自适应路由算法，不会根据当前测量或者估计的流量和拓扑结构，来调整他们的路由决策，所使用的路由选择是预先在离线情况下计算好的。

动态路由算法：自适应路由算法，根据当前的流量和拓扑结构的变化，自动改变路由决策。

最短路径路由算法：静态算法。跳数或物理距离或其他某种准则。路由算法可以根据任何一种准则或者多种准则的组合来计算“最短”（不一定是物理最短）路径。

扩散法：静态算法。每一个进来的分组将被发送到除了进来的那条线路之外的每一条输出线路上。为避免大量的重复分组，一种方法是在每个分组的头中包含一个跳计数器，每经过一跳该值减1，等于0时该分组被丢弃。另一种做法是记录已经扩散过的分组。一种实用的扩展是选择性扩展算法。

距离矢量路由算法：动态路由算法。每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标路由器的最佳距离，以及所使用的线路。通过在邻居路由器之间相互交换信息，路由器不断更新自己内部的表。缺陷是无穷计算问题，导致需要很长时间才能收敛到稳定状态。引起的原因在于，当X告诉Y他有一条路径通向Z的时候，Y无从知道Y自己是否就在这条路径上。

链路状态路由算法：动态路由算法，替代了距离矢量路由算法。其思想为：

（1）发现他的邻居节点，并知道其网络地址。

（2）测量到各邻居节点的延迟或者开销。

（3）构造一个分组，分组中包含所有他刚刚知道的信息。

（4）将这个分组发送给所有其他的路由器。

（5）计算出到每一个其他路由器的最短距离

六、什么是标准路由选择算法？

路由选择算法在网络路由器中运行、交换和计算信息，用这些信息配置转发表。主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器,又称为该主机的第一跳路由器。每当主机发送一个分组时，该分组被传送给它的默认路由器。将源主机的默认路由器称作源路由器，把目的主机的默认路由器称作目的路由器。一个分组从源主机到目的主机的路由选择问题显然可归结为从源路由器到目的路由器的路由选择问题。

路由选择算法的目的是简单的，给定一组路由器以及连接路由器的链路，路由选择算法要找到一条从源路由器到目的路由器的"好"路径。通常，一条好路径指具有最低费用的路径。

七、DV路由算法基本原理？

DV算法是一个很巧妙的路由算法，它实际上利用了很多算法设计的技巧，包括但不限于分散式计算，迭代优化思想以及逼近不动点的思想。

分散式计算在于每一个路由器，实际上都不知道整个网络是什么样子，它们只是在和自己的相邻路由器进行“沟通”，这样很大程度上简降低了这一算法的实现难度以及逻辑上的复杂度。

迭代优化和逼近不动点是不可分割的，通过每一次迭代计算，来获取可能存在的、更优的路径结果，直至最后不动点——稳定路由表的抵达，算法也就完成了它的工作。

八、Ospf协议使用的路由算法是？

OSPF协议的路由器，采用的路由计算的算法是Dijkstra算法。

算法描述如下：

第一步：把Root加入最小树，并设Root可直达的顶点为候选人。

第二步：若候选人列表为空，则最小树生成，否则候选人列表中选取花费最小的，加入到最小树中。

第三步：把新加入的顶点所能直达的顶点列为候选人。

第四步：在候选人名单中除去最小树中已经出现的，返回到第二步。

工作过程：

通过LSDB可得到个顶点的连接状态，利用Dijkstra算法有"内"向外，从区域内到区域间，从AS内到AS外，诼步生成最小树，进而生成路由表。

路由计算过程：

首先判断区域是否为NULL，是的话结束。否则计算区域内路由，区域间路由，用转换区域改进路由，计算AS外部路由，取下一区域，返回开始部分（判断该区域是否为NULL.....）。

九、dsdv路由协议采用了什么算法？

DSDV应该算是Ad-hoc中经典的先应式路由协议。

1、协议采用最短路径法则，每个节点维护一张包含到达节点的路由信息的路由表，并根据每个节点broadcast来update router table来适应网络的拓扑变化。

2、协议中使用目的端的端顺序号，避免因使用过时的路由信息而产生无效的路径（包括路由环路和终端的路径）。

3、每个目标节点的路由记录对应一个目的地序列号，这个序列号由目标节点产生。

4、当节点从邻节点的距离/向量报文中得到某一目标节点的另一个路由记录时，若新记录的顺序号比已有的记录大，则节点使用新的路由记录。

5、若2个路由记录的顺序号相同，则节点使用路径长度更短的记录；否则，目标节点的记录不变。通过摘要信息中的序列号字段就可以了，这个序列号是个长32位的字段，最小的一个序列号是0X80000001，最大的是0X8FFFFFFF。当序列号越大的时候，就表示越新！dsdv路由协议采用的算法详细介绍完毕

十、路由表更新算法例题？

RIP协议距离向量算法——路由表更新

题目：

假定网络中的路由器B的路由表有如下的项目（这三列分别表示“目的网络”、“距离”和“下一跳路由器”）：

B的路由表

目的网络 距离 下一跳路由器

N1 7 A

N2 2 C

N6 8 F

N8 4 E

N9 4 F

现在B收到从C发来的路由信息（这两列分别表示“目的网络”“距离”）：

B收到C发来的路由信息

目的网络 距离

N2 4

N3 8

N6 4

N8 3

N9 5

解决步骤：

1.对新接收到的路由表进行更新，全部"距离"+1，且"下一跳路由器"都写成发送方路由器的名称(这里是C给B发的路由表，所以下一跳名称填C)

B收到C发来的路由信息（新表）

目的网络 距离 下一跳路由器

N2 5 C

N3 9 C

N6 5 C

N8 4 C

N9 6 C

2.开始对比新表和B的路由表

1.看目的网络

如果是新的目的网络，则直接把对应的各项信息填入表中；如果是相同的目的网络（"新表"和"B路由表"对比），继续下面步骤。

2.看下一跳路由器

相同的目的网络为前提，看下一跳路由器。如果下一跳路由器相同，就更新(用新表的)。如果下一跳路由器不同，继续下面步骤。

3.看距离

如果距离不同，谁距离短，选谁来更新；如果距离相同，不更新。

路由器B更新后的路由表（答案）

目的网络 距离 下一跳路由器 说明

N1 7 A 无新信息，不改变

N2 5 C 相同的下一跳，更新

N3 9 C 新的项目，添加进来

N6 5 C 不同的下一跳，距离更短，更新

N8 4 E 不同的下一跳，距离一样，不改变

N9 4 F 不同的下一跳，距离更大，不改变