ls路由的无穷计数
如果您想了解有关ls路由的无穷计数的更多信息，那么您来到了正确的地方。在本文中，我们将详细介绍链路状态路由算法存在无穷计数问题方面的内容，并为您提供一些有用的知识。记得将我们的网站添加到收藏夹中，以获取更多相关的信息。
本文目录一览：
路由算法的度量标准
路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度量、再填入路由表中，作为寻径的标准。
通常所使用的度量有：路径长度、可靠性、时延、带宽、负载、通信成本等。 采用LS算法时，每个路由器必须遵循以下步骤：
1、确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息，其中包含它自身的IP地址。
2、测量相邻路由器的延时（或者其他重要的网络参数，比如平均流量）。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，路由器便可以计算出延时。（路程往返时间是网络当前延迟的量度，通过一个分组数据包从远程主机返回的时间来测量。）该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。
3、向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。
在这一步中，所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够知道网络的结构以及状态。
4、使用一个合适的算法，确定网络中两个节点之间的最佳路由。
在这一步中，路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点，如Dijkstra最短路径算法。在这个算法中，一个路由器通过收集到的其他路由器的信息，建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注，称为权值或成本。这个数字是延时和平均流量的函数，有时它仅仅表示节点间的跃点数。例如，如果一个节点与目的地之间有两条链路，路由器将选择权值最低的链路。 Dijkstra算法执行下列步骤：1、路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i, j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。
2、路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：
前序字段——表示当前节点之前的节点。
长度字段——表示从源节点到当前节点的权值之和。
标号字段——表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。
3、路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。
4、路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。
5、路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
6、路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
7、如果这个节点不是V2（目的节点），路由器则返回到步骤5。
8、如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。 距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面，链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些。
dv算法为什么比较小规模
在DV算法中，每个节点仅与它的直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中（它所知道的）所有其他节点的最低开销估计。LS算法需要全局信息，每个节点（经广播）与所有其他节点通信，但仅告诉它们与它直接相连链路的开销。
报文复杂性：LS算法要求每个节点都知道网络中每条链路的开销，这就要求要发送O(|N||E|)个报文，而且无论何时一条链路的开销改变时，必须向所有节点发送新的链路开销。DV算法要求在每次迭代时，在两个直接相连邻居之间交换报文，而且仅当在新的链路开销导致与该链路相连节点的最低开销路径发生改变时，才传播已改变的链路开销。
收敛速度：LS算法是一个要求O(|N||E|)个报文的O(|N|2)算法。DV算法收敛较慢，且在收敛时会遇到路由选择环路、无穷计数问题。
健壮性：在LS算法下，路由计算在某种程度上是分离的，提供了一定程度的健壮性。DV算法中一个不正确的节点计算值会扩散到整个网络
路由算法的类型有
路由算法有很多种，如果从路由表对网络拓扑和通信量变化的自适应能力的角度划分，可以分为静态路由算法和动态路由算法两大类，这两大类又可细分为几种小类型，比较典型常见的有以下几种：
一、静态路由算法
1.Dijkstra算法（最短路径算法）
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。
Dijkstra算法执行步骤如下：
步骤一：路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i,j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。
步骤二：路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：
前序字段———表示当前节点之前的节点。
长度字段———表示从源节点到当前节点的权值之和。
标号字段———表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。
步骤三：路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。
步骤四：路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。
步骤五：路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
步骤六：路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
步骤七：如果这个节点不是V2（目的节点），路由器则返回到步骤5。
步骤八：如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。
2.扩散法
事先不需要任何网络信息；路由器把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。将来会有多个分组的副本到达目的地端，最先到达的，可能是走了“最优”的路径常见的扩散法是选择性扩散算法。
3.LS算法
采用LS算法时，每个路由器必须遵循以下步骤：
步骤一：确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息，其中包含它自身的IP地址。
步骤二：测量相邻路由器的延时（或者其他重要的网络参数，比如平均流量）。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，路由器便可以计算出延时。（路程往返时间是网络当前延迟的量度，通过一个分组数据包从远程主机返回的时间来测量。）该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。
步骤三：向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。
在这一步中，所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够知道网络的结构以及状态。
步骤四：使用一个合适的算法，确定网络中两个节点之间的最佳路由。
路由算法有哪些类型？路由算法与路由协议的区别
在这一步中，路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点，如Dijkstra最短路径算法。在这个算法中，一个路由器通过收集到的其他路由器的信息，建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注，称为权值或成本。这个数字是延时和平均流量的函数，有时它仅仅表示节点间的跃点数。例如，如果一个节点与目的地之间有两条链路，路由器将选择权值最低的链路。
二、动态路由算法
1.距离向量路由算法
距离向量路由算法，也叫做最大流量演算法，其被距离向量协议作为一个算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量，等等。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。其优点是算法简单容易实现。缺点是慢收敛问题，路由器的路径变化需要像波浪一样从相邻路由器传播出去，过程缓慢。
每一个相邻路由器发送过来的路由表都要经过以下步骤：
步骤一：对地址为X的路由器发过来的路由表，先修改此路由表中的所有项目：把”下一跳”字段中的地址改为X，并把所有”距离”字段都加1。
步骤二：对修改后的路由表中的每一个项目，进行以下步骤：
（1）将X的路由表(修改过的)，与S的路由表的目的网络进行对比。若在X中出现，在S中没出现，则将X路由表中的这一条项目添加到S的路由表中。
（2）对于目的网络在S和X路由表中都有的项目进行下面步骤：
1）在S的路由表中，若下一跳地址是x，则直接用X路由表中这条项目替换S路由表中的项目。
2）在S的路由表中，若下一跳地址不是x，若X路由表项目中的距离d小于S路由表中的距离，则进行更新。
步骤三：若3分钟还没有收到相邻路由器的更新表，则把此相邻路由器记为不可到达路由器，即把距离设置为16。
2.链路状态最短路由优先算法SPF
1）发现邻居结点，并学习它们的网络地址；
2）测量到各邻居节点的延迟或者开销；
3）创建链路状态分组；
4）使用扩散法发布链路状态分组；
5）计算到每个其它路由器的最短路径。
计算机网络自学笔记：选路算法
网络层必须确定从发送方到接收方分组所经过的路径。选路就是在网络中的路由器里的给某个数据报确定好路径(即路由)。
一 台主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器，又称为该主机的默认网关。 每当某主机向外部网络发送一个分组时，该分组都被传送给它的默认网关。
如果将源主机的默认网关称为源路由器,把目的主机的默认网关称为目的路由器。为一个分组从源主机到目的主机选路的问题于 是可归结为从源路由器到目的路由器的选路问题。
选路算法的目标很简单:给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的最好路径，通常一条好路径是指具有最低费用的路径。
图 G=(N，E)是一个 N 个节点和 E 条边的集合，其中每条边是来自 N 的一对节点。在网 络选路的环境中，节点表示路由器，这是做出分组转发决定的节点，连接节点的边表示路由 器之间的物理链路。
一条边有一个值表示它的费用。通常一条边的费用可反映出对应链路的物理长度、链路速度或与该链路相关的费用。
对于 E 中的任一条边(xy)可以用 c(xy )表示节点 x 和 y 间边的费用。一般考虑的都是无向 图，因此边(xy)与边(y x)是相同的并且开销相等。节点 y 也被称为节点 x 的邻居。
在图中为各条边指派了费用后，选路算法的目标自然是找出从源到目的间的最低费用路径。图 G=(N，E)中的一条路径(Path)是一个节点的序列，使得每一对以(x1,x2)， (x2,x3)，…，是 E 中的边。路径的费用是沿着路径所有边费用的总和。
从广义上来说，我们对 选路算法分类的一种方法就是根据该算法是全局性还是分布式来区分的。
.全局选路算法： 用完整的、全局性的网络信息来计算从源到目的之间的最低费用路径。
实际上， 具有全局状态信息的算法常被称作链路状态 LS 算法， 因为该算法必须知道网络中每条链路的费用。
.分布式选路算法： 以迭代的、分布式的方式计算出最低费用路径。通过迭代计算并与相邻节点交换信息，逐渐计算出到达某目的节点或一组目的节点的最低费用路径。
DV 算法是分布式选路算法， 因为每个节点维护到网络中的所有其他节点的费用(距离)估计的矢量。
选路算法的第二种广义分类方法是根据算法是静态的还是动态的来分类。
一： 链路状态选路算法 LS
在链路状态算法中，通过让每个节点向所有其他路由器广播链路状态分组， 每个链路状态分组包含它所连接的链路的特征和费用， 从而网络中每个节点都建立了关于整个网络的拓扑。
Dijkstra 算法计算从源节点到网络中所有其他节点的最低费用路径.
Dijkstra 算法是迭代算法，经算法的第 k 次迭代后，可知道到 k 个目的节点的最低费用路径。
定义下列记号:
D(V)随着算法进行本次迭代，从源节点到目的节点的最低费用路径的费用。
P(v)从源节点到目的节点 v 沿着当前最低费用路径的前一节点(，的邻居)。
N`节点子集；如果从源节点到目的节点 v 的最低费用路径已找到，那么 v 在 N`中。
Dijkstra 全局选路算法由一个初始化步骤和循环组成。循环执行的次数与网络中的节点个数相同。在结束时，算法会计算出从源节点 u 到网络中每个其他节点的最短路径。
考虑图中的网络，计算从 u 到所有可能目的地的最低费用路径。
.在初始化阶段 ，从 u 到与其直接相连的邻居 v、x、w 的当前已知最低费用路径分别初始化为 2，1 和 5。到 y 与 z 的费用被设为无穷大，因为它们不直接与 u 连接。
.在第一次迭代时， 需要检查那些还未加到集合 N`中的节点，找出在前一次迭代结束时具有最低费用的节点。那个节点是 x 其费用是 1，因此 x 被加到集合 N`中。然后更新所有节点的 D(v)，产生下表中第 2 行(步骤)所示的结果。到 v 的路径费用未变。经过节点 x 到 w 的 路径的费用被确定为 4。因此沿从 u 开始的最短路径到 w 的前一个节点被设为 x。类似地， 到 y 经过 x 的费用被计算为 2，且该表项也被更新。
.在第二次迭代时 ，节点 v 与 y 被发现具有最低费用路径 2。任意选择将 y 加到集合 N` 中，使得 N’中含有 u、x 和 y。通过更新，产生如表中第 3 行所示的结果。
.以此类推…
当 LS 算法结束时，对于每个节点都得到从源节点沿着它的最低费用路径的前继节点， 对于每个前继节点，又有它的前继节点，按照此方式可以构建从源节点到所有目的节点的完 整路径。
根据从 u 出发的最短路径，可以构建一个节点(如节点 u)的转发表。
二 距离矢量选路算法 DV
LS 算法是一种使用全局信息的算法，而距离矢量算法是一种迭代的、异步的和分布式的算法。
Bellman-Ford 方程：
设 dx(y)是从节点 x 到节点 y 的最低费用路径的费用，则有 dx(y) = min {c(x,v) + dv(y) }
PS： 方程中的 min，是指取遍 x 的所有邻居。
Bellman-Ford 方程含义相当直观，意思是从 x 节点出发到 y 的最低费用路径肯定经过 x 的某个邻居，而且 x 到这个邻居的费用加上这个邻居到达目的节点 y 费用之和在所有路径 中其总费用是最小的。 实际上，从 x 到 v 遍历之后，如果取从 v 到 y 的最低费用路径，该路 径费用将是 c(x,v)+ dv(y)。因此必须从遍历某些邻居 v 开始，从 x 到 y 的最低费用是对所有邻 居的 c(x,v)+dv(y)的最小值。
在该 DV 算法中，当节点 x 看到它的直接相连的链路费用变化，或从某个邻居接收到一 个距离矢量的更新时，就根据 Bellman-Ford 方程更新其距离矢量表。
三 LS 与 DV 选路算法的比较
DV 和 LS 算法采用不同的方法来解决计算选路问题。
在 DV 算法中，每个节点仅与它的直接相连邻居交换信息，但它为它的邻居提供了从其 自己到网络中(它所知道的)所有其他节点的最低费用估计。
在 LS 算法中，每个节点(经广播)与所有其他节点交换信息，但它仅告诉它们与它直接 相连链路的费用。
·报文复杂性：
LS 算法要求每个节点都知道网络中每条链路的费用，需要发送 O(nE)个消息。
DV 算法要求在每次迭代时，在两个直接相连邻居之间交换报文，算法收敛所需的时间 依赖于许多因素。当链路费用改变时，DV 算法仅当在会导致该节点的最低费用路径发生改 变时，才传播已改变的链路费用。
·收效速度：
DV算法收敛较慢，且在收敛时会遇到选路环路。DV算法还会遭受到计数到无穷的问题。
•健壮性： 在 LS 算法中，如果一台路由器发生故障、或受到破坏，路由器会向其连接的链路广播 不正确费用，导致整个网络的错误。
在 Dv 算法下， 每次迭代时，其中一个节点的计算结果会传递给它的邻居，然后在下次迭代时再间接地传递给邻居的邻居。在这种情况下，DV 算法中一个不正确的计算结果也会扩散到整个网络。
四.层次选路
两个原因导致层次的选路策略：
•规模： 随着路由器数目增长，选路信息的计算、存储及通信的开销逐渐增高。
•管理自治： 一般来说，一个单位都会要求按自己的意愿运行路由器(如运行其选择的某 种选路算法)，或对外部隐藏其内部网络的细节。
层次的选路策略是通过将路由器划分成自治系统 AS 来实施的。
每个 AS 由一组通常在相同管理控制下的路由器组成(例如由相同的 ISP 运营或属于相同 的公司网络)。在相同的 AS 内的路由器都全部运行同样的选路算法。
在一个自治系统内运行的选路算法叫做自治系统内部选路协议。 在一个 AS 边缘的一台 或多台路由器，来负责向本 AS 之外的目的地转发分组，这些路由器被称为网关路由器
在各 AS 之间，AS 运行相同的自治系统间选路协议。
第四章 网络层
1.转发。当一个分组到达路由器的一条输入链路时，路由器必须将该分组移动到适当的输出链路。
2.路由选择。当分组从发送方流向接收方时，网络层必须决定这些分组所采用的路由或路径。
3.每台路由器都有一张转发表，链路层交换机基于链路层字段中的值做转发决定，路由器则是基于网络层的字段
4.连接建立
1.确保交付
2.具有延时上界的确保交付
3.对于分组流：（1）有序分组交付（2）确保最小带宽（3）确保最大时延抖动（4）安全性服务
4.因特网提供的是尽力而为服务（best-effort service）
5.两个重要的ATM服务模型：（1）恒定比特率ATM网络服务CBR（2）可用比特率ATM网络服务ABR
1.仅在网络层提供连接服务的计算机网络称为虚电路VC网络；仅在网络层提供无连接服务的计算机网络称为数据报网络。
1.每个数据报都带有VC标识
2.网络的路由器必须为进行中的连接维持连接状态信息
3.虚电路中有3个明显的不同阶段：（1）虚电路建立（2）数据传送（3）虚电路拆除
4.相比与运输层的连接（只有两个端系统知情，路由器完全不知道），虚电路的连接，沿两个端系统之间路径上的路由器都要参与虚电路的建立，且每台路由器都完全知道经过它的所有虚电路。
5.信令报文/信令协议
1.路由器用目的地址的前缀与转发表中的表项进行匹配
2.转发表能够在任何时刻被修改
1.因特网服务模型使服务保证最少
1.路由器的四个组成部分：（1）输入端口，物理接口（2）交换结构（3）输出端口（4）路由选择处理器
1.经内存交换，吞吐量小于B/2，B为内存单位时间读写分组数
2.经总线交换，吞吐量为1
3.经互联网络交换，如纵横交换，克服总线带宽限制
1.输出端口排队，需要的缓存空间为 ，C为链路容量，N为TCP流。
2.输出端口排队就需要分组调度程序，用于挑选一个来发送，提供了服务质量保证。
3.缓存填满前就丢弃一个分组，以便向发送方提供一个拥塞信号。主动队列管理
1.线路前部阻塞，即本身是可以发送的，但前一个阻塞了。
1.网络范围的路由选择控制平面因此是分布式的
1.路由选择协议2.IP协议3.ICMP协议
1.首部检验和只检验首部，而TCP/UDP检验和是对整个报文段进行的。
1.一个链路层帧能承载的最大数据量叫做最大传送单元MTU。
2.标识、标志和片偏移字段。最后一个片的标志比特被设为0，其他的标志比特被设为1
1.点分十进制法
2.子网，如223.1.1.0/24，/24称为子网掩码
3.因特网的地址分配策略被称为无类别域间路由选择CIDR，对于子网可以写作a,b,c,d/x
4.分类编址，A类（/8）、B类（/16）、C类（/24）
5.广播地址，全为1
ICANN
1.动态主机配置协议DHCP，即插即用协议。每个子网都有DHCP服务器。DHCP可以返回子网掩码、第一跳路由地址（默认网关）以及本地DNS服务器地址
2.DHCP客户-服务器交互四个步骤：（1）DHCP服务器发现，目的IP为广播，封装在UDP里（2）DHCP服务器提供，目的IP为广播，返回给用户推荐的地址、网络掩码以及IP地址租用期（3）DHCP请求（4）DHCP ACK
1.NAT转换表，端口号和IP地址转换
2.NAT是有争议的。如修改端口号，路由器应当处理第三层分组，NAT违反了端到端原则，可以直接用IPv6
3.存在NAT之外的客户端要访问NAT之内的服务器存在问题。
为某些请求的公共端口号请求一个NAT映射，位于（专用IP地址，专用端口号）和（公共IP地址，公共端口号）之间
也可以使用外部服务器中继的方式解决
1.ICMP最典型的用途是差错报告。被主机和路由器用来彼此沟通网络层的信息。ICMP报文是承载在IP分组中的
2.Traceroute程序是由ICMP报文实现的。
3.源主机将一系列普通IP数据报发送到目的地，每个都携带了一个不可达的UDP端口号和UDP报文段，并设置第一个数据报的TTL为1，第二个为2...；当第n个数据报到达第n个路由器时，则返回第n台路由器的名字与IP地址.目的主机向源地主发送一个不可达的ICMP报文来结束发送UDP报文
流标签：给属于特殊流的分组加上标签
跳限制：每经过一个路由器跳限制减1
1.双栈dual-stack，会发生IPv4到IPv6转换过程中信息的丢失
2.建隧道tunneling（一种双栈方法）可以解决，将IPv6数据报封装进IPv4的数据中，等到接收端的IPv6接收到之后再从数据中取出来
1.全局式路由选择算法，常被称作链路状态算法LS/分散式路由选择算法，距离向量算法DV
2.也可以分为静态路由算法和动态路由算法
3.分为负载敏感和负载迟钝
1.网络拓扑和所有链路费用都是已知的。
2.Dijkstra算法和prim算法
3.Dijkstra算法时迭代算法，经过k次迭代，可知到k个结点的最低费用路径。
D（v）:到算法的本次迭代，从源结点到目的结点v的最低费用路径的费用
p（v）:从源到v沿着当前最低费用路径的前一结点
N‘：结点子集；如果从源到v的最低费用路径已经确定，则v在N'中
复杂度为 ,但可以优化到 ，有可能发生振荡（如果费用等于承载的负荷）
1.每个结点都要从一个或多个直接相连邻居接收某些信息，执行结算，然后将其结果分发给邻居。
2.DV算法是一个迭代的、异步的和分布式的算法
3.
4.如果x的距离向量更新了就向每个邻居发送其更新后的距离向量。
当其中一个路径变大时可能要迭代很多次才能全部更新一致（先更新在发送消息）
如果z通过y到达x,则z将告诉y，它到x的距离是无穷大
1.报文复杂性。LS算法要求发送O(NE)个报文，DV算法只要给邻居发送
2.收敛速度。LS算法O（N^2），DV算法很慢，还会遇到无穷计数问题
3.健壮性。LS算法是分离的，DV算法会将不正确的结点计算值扩散到整个网络。
1.自治系统AS。在相同的AS中的路由器全部运行相同的路由算法，且拥有彼此的信息
2.连接不同的AS的路由器叫网关路由器。
3.当一个AS连有多个AS时，该AS需要知道多个AS的目的地并把信息告诉该AS中的每个路由器。
4.如果多个网关都可达则选择费用最小的（热土豆法）
1.内部网关协议
2.路由选择信息协议RIP和开放最短路优先OSPF
3.在RIP中，路由选择更新信息在邻居之间通过使用一种RIP响应报文来交换
4.路由选择表
5.每隔30s，路由器会根据收到的通告更新转发表
6.如果过了180s没有收到邻居的报文，则可以认为该邻居将不再是可达的了。此时该路由器修改转发表并告知可达的邻居。也可以通过RIP请求报文，请求其邻居到指定目的地的费用（在UDP上使用端口520互相发送RIP报文）。
7.RIP在UNIX中是被当作应用层进程来实现的。
1.OSPF的核心就是一个使用洪泛链路状态信息的链路状态协议和一个Dijkstra最低费用路径算法。
2.OSPF的优点：（1）安全（2）多条相同费用的路径（3）对单播或多播路由选择的综合支持（4）支持在单个路由选择域内的层次结构
边界网关协议
1.BGP为每个AS提供一下工作的手段：（1）从相邻AS处获得子网可达性信息。（2）向本AS内部的所有路由器传播这些可达性信息（3）基于可达性信息和AS策略，决定到达子网的路由
1.半永久TCP连接来交换路由选择信息，对于每条连接的两台路由器称为BGP对等方，整个连接称为BGP会话，包括外部会话和内部会话
2.在BGP中目的地不是主机而是CIDR化的前缀
3.当一台路由器得知一个新前缀时，它为该前缀在其转发表中创建一个项
1.一个自治系统由全局唯一的自治系统号所标识
2.当一台路由器通过BGP会话通告一个前缀时，它在前缀中包括一些BGP属性。带有属性的前缀称为一条路由。两个较为重要的属性是AS-PATH（前缀通告已经通过的AS）和NEXT-HOP
3.当一台网关路由器接收到一台路由通告时，它使用其输入策略来决定是否接收或过滤该路由，是否设置某种属性
1.BGP顺序调用下列消除规则，直到留下一条路由。
（1）路由被指派一个本地偏好值作为它们的属性之一
（2）在余下的路由中，具有最短AS-PATH的路由将被选择
（3）选择具有最靠近NEXT-HOP路由器的路由
（4）使用BGP标识符来选择路由
（1）OPEN（2）UPDATE（3）KEEPLIVE（4）NOTIFICATION
X不会告诉B，X能经过C到达Y，因此B也不会经过X转发目的地为C或Y的流量
对于提供商网络，比如B知道A能到W，B就会告诉X经过BA能到W，但B不会告诉C，A能到W，防止X走CA到W
ls与dv选路算法的比较 和 ipv4与ipv6的比较
在DV算法中，每个节点仅与它的直接邻居交谈，但它为它的邻居提供了从其自己到网络中（它所知道的）所有其他节点的最低费用估计。
在LS算法中，每个节点（经广播）与所有其他节点交谈，但它仅告诉他们与它直接相连链路的费用。
a 报文复杂性，LS算法大于DV算法
b 收敛速度，LS快于DV算法，DV算法在收敛时会遇到选路环路，还会遇到计数到无穷的问题。
c 健壮性，LS好于DV
通过这些技巧，您可以更好地控制您的路由器，以获得更快的网络速度和更安全的网络连接。
