路由算法的特征
今天给各位分享路由算法涉及到树的知识，其中也会对路由算法的特征进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、链路状态路由算法的算法工作原理
2、路由算法
3、什么是路由啊 路由的组成 以及路由的算法
4、OSPF路由算法
5、有谁能讲下？路由有几种算法？各有什么优缺点？
链路状态路由算法的算法工作原理
链路状态选路算法的工作原理如下
（1）在参与链路状态选路的路由器集合中，每个路由器都需要通过某种机制来了解自己所连接的链路及其状态。
（2）各路由器都能够将其所连接的链路的状态信息通知给网络中的所有其他路由器，这些链路信息包括链路状态、费用以及链路两端的路由器等。
（3）链路状态信息的通过链路状态分组（LSP）来向整个网络发布。一个LSP通常包含源路由器的标识符、相邻路由器的标识符，以及而知之间链路的费用。每一个LSP都将被网络中的所有的路由器接收，并用于建立网络整体的统一拓扑数据库。由于网络中所有的路由器都发送LSP，经过一段时间以后，每一个路由器都保持了一张完整的网络拓扑图，再在这个拓扑图上，利用最短通路算法（例如Dijkstra算法等），路由器就可以计算出从任何源点到任何目的地的最佳通路。
这样，每一个路由器都能够利用通路最短的原则建立一个以本路由器为根、分支到所有其他路由器的生成树，依据这个生成树就可以很容易地计算出本路由器的路由表。
路由算法
路由算法是网络层软件的一部分。子网提供数据报服务，每个包都要做路由选择；子网提供虚电路服务，只需在建立连接时做一次路由选择
正确性，简单性，健壮性（鲁棒性，网络出现意外情况时候的解决问题的能力。例如突然某个路由器停电了，使得周边的路由器都没法正常工作，如果出现这样的问题说明路由器的健壮性不够），稳定性（常规使用是否稳定，数据量增多的时候能否正常工作），公平性（网络资源的使用是否公平，避免有些节点出现特别繁忙的状态，而有些节点总是处于很闲的状态），最优性
1.全路路由（广播路由）算法：如洪泛算法，按照所有路径广播转发（中间转发节点以及目标节点都会送到很多重复数据。不需要路由表和路由控制功能）
2.多路路由算法：向所有接近目的节点的路径转发（中间转发节点以及目标节点都会送到很多重复数据。）
3.单路路由算法：如距离矢量算法，向目的节点沿着唯一的路径转发（中间的转发节点只转发一份数据即可）
• 按健壮性和简单性划分
1.非自适应算法（静态路由算法）：不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表。需要人为的更改和设定。特点是简单、开销小、灵活性差。典型算法为基于流量的路由算法等
2.自适应算法（动态路由算法）：可根据网络流量（网络承载的数据量）和拓扑结构的变化更新路由表。特点是开销大、健壮性和灵活性好。典型算法为距离向量路由算法、链路状态路由算法等
☆可以静态路由和动态路由结合起来使用，此时静态路由的优先级别较高
测量（获取）有关路由选择的网络度量参数（选择最优，比如是要求传播距离最短，还是要求传输时延短等）。如何测量？选取哪些网络参数？
将路由信息传送到适当的网络节点。传送给谁？如何传送？传送什么信息？
计算和更新路由表。更新路由表的算法
根据新路由表执行分组的转发
如果路由器J在路由器I到K的最优路由上，那么从J到K的最优路由一定落在同一路由上
从所有的源节点到一个给定的目的节点的最优路由的集合形成了一个以目的节点为根的树，称为汇集树；路由算法的目的是找出并使用汇集树
基本思想：构建子网的拓扑图，图中的每个节点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法需要在图中找出节点间的最短路径
节点数量；地理距离；传输延迟；距离、信道带宽等参数的加权函数
网络规模增大带来的问题：路由器中的路由表增大；路由器为选择路由而占用的内存、CPU时间和网络带宽增大
分层路由：分而治之的思想；根据需要，将路由器分成区域、聚类、区和组；Fig.6-6，路由表由17项减为7项
分层路由带来的问题：路由表中的路由不一定是最优路由
☆分层路由功能大部分时候性能是比较好的，可以选择最优路径，但是有时也会选择到非最优路径。比如上图中如果想从1A到5C，应该是1A→1B→2A→2B→2D→5C是比较优的选择，但是按照1A的分层路由表显示，从区域1到区域5出口线路为1C，因此选择的路线为1A→1C→3B→4A→5A→5B→5C，这时就相对绕远了
DVR - Distance Vector Routing
动态路由算法，也称Bellman - Ford路由算法或Ford - Fulkerson算法，最初用于ARPANET（Internet的前身），被RIP协议所采用
每个路由器维护一张路由表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；每隔一段时间，路由器向所有邻居节点发送它到每个目的节点的距离表，同时它也接收每个邻居节点发来的距离表；邻居节点X发来的表中，X到路由器I的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表
图1：
此时路由A把它的路由表发给路由B，B会综合从A得来的路由表来更新自己的矢量表↓
根据初始A矢量表和B矢量表得知B到A为6，B到C为1，B到D没有；两个表都有到E的距离，直接从B到E为8；如果B经由A再到E就要计算A到B的距离加上A到E的距离即可，即6+1=7
图2：
B把路由表发给C之后↓
从C的初始矢量表可得知C到B为1，C到D为2，C无法直接到A，但是通过B的路由表得知B到A为6，再加上C到B的距离1，得出C到A距离为7，同理可得到E距离为7+1=8
图3：
C把路由表发给D之后↓
图4：
D把路由表发给E之后↓
J的相邻节点为4个，分别为A，I，H，K，因此可以选择的路线也为4种
现在要求J的最新路由表。以J到E为例，J到A为8，A到E为14，和为22；J到I为10，I到E为7，和为17；J到H为12，H到E为30，和为42；J到K为6，K到E为22，和为28。从而得出，经由I的时候得到的和17最小，因此在新生成的J到E的位置记录17
无限计算问题：对好消息反应迅速，对坏消息反应迟钝
比如从E到A，E刚开始连通的时候是不知道如何才能到A的，只有通过B与A交互，C与B交互这样最终E通过与D交互才知道如何能到A，这就是好消息。可能需要花些时间，但是结果都是无论目的节点是哪里总会找到路径
坏消息例子：A，B，C之间通信。B到A的距离为1（A，1），C到A的距离为2（B（经B），2）。各个节点都会有一个刷新周期，到了这个周期的时候每个节点会把自己的路由信息发给其相邻节点。例如A路由断开连接，这个时候B到A的线路断开。也就是B到A的距离为无穷大了（A，∞）。如果在B把这个信息反馈给C之前，C先把路由信息告诉B了，那么B收到的信息就为（C，3）。因为A已经不存在，而B从C处得知通过C有路径可以到达A，这时B的路由表就变成（C，3），同样的这时B再告诉C，C就会变成（B，4），就会这样无穷计算下去。如果一开始是B先把信息发给C就不会发生这样的问题
• 触发式更新：节点不等到刷新周期的到来，只要有突发情况马上就会把情况通知相邻路由
• 水平分割：因为一开始C是从B得知经过B可以到达A的，所以用了这种方法之后，C就不会再向B发送如何到A，而只等着B给C发如何到A了。这样就不会有无穷计算问题
• 定义一个最大值：坏消息例子当中，括号里后面的数会一直循环增长下去，如果把这个数字设置一个最大值，那么当循环到这个最大值的时候双方就不会再就怎么到A的信息进行交互了，就不会发生无穷计算的情况
• 挂起计数器：坏消息例子当中，B收到了C的路由最新信息（C，3）的时候这个不会马上生效刷新，（A，∞）会保留两个周期，在这两个周期里面，B肯定有机会给C发送（A，∞），
而因为C没有通往A的路径，所以当C到刷新周期的时候给B发的就为（B，∞）。B前后收到的信息不一致，但是第二次收到的信息和B发给C的信息是一致的，所以B就会认为第一次收到的（C，3）是无效的。但是如果C真的有了一条通往A的线路，这时两次发的信息一定是一致的，那么B就会相信C的信息，从而把（A，∞）刷新成C给B的信息
❉距离向量路由算法只适用于小规模网络，每个节点不清楚整个网络的拓扑结构
发现邻居节点，并学习它们的网络地址，测量到每个邻居节点的延迟或开销，将所有学习到的内容封装成一个链路状态包（包以发送方的标识符开头，后面是序号、年龄和一个邻居节点列表；链路状态包定期创建或发生重大事件时创建）。将链路状态包广播发送给所有其他路由器【洪泛方式：状态包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的则分发，若是重复的则丢弃，若序号比路由记录中的最大序号小则认为过时而丢弃】。计算到每个其他路由器的最短路径
☆链路状态路由算法适用于大规模网络。每个节点都会了解其他节点的局部拓扑，因此就会了解整个网络的拓扑结构，这时当前节点就能找到到目的节点的最优路由
• 使用32位序号。
因为序号是循环使用的，如果位数很少，比如只是1~7，那么7不一定比1大，1有可能是下一轮的第一个数。而32位的时候因为数字特别庞大，不会出现这样问题
• 增加年龄域，每秒钟年龄减1，为零则丢弃
比如A发给B （C，4），由于差错，本来是（C，5）的下一个包，变成了（C，1000）。这之后来的（C，6），（C，7）。。。都没有（C，1000）大，因此包会被丢弃。但其实后面到的包都是新的。为了避免这样的问题发生，（C，1000）里的1000就会在每一秒减1，直到年龄比新到的包小，接下来就可以正常接包了。不过这之前到的包都会被丢弃，这也是没有办法的事
• 链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包
• 链路状态包需要应答
为了保证数据传输的可靠性
什么是路由啊 路由的组成 以及路由的算法
路由：路由（routing）是指分组从源到目的地时，决定端到端路径的网络范围的进程。路由工作在OSI参考模型第三层——网络层的数据包转发设备。路由器通过转发数据包来实现网络互连。虽然路由器可以支持多种协议（如TCP/IP、IPX/SPX、AppleTalk等协议），但是在我国绝大多数路由器运行TCP/IP协议。路由器通常连接两个或多个由IP子网或点到点协议标识的逻辑端口，至少拥有1个物理端口。路由器根据收到数据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳地址，并且重写链路层数据包头实现转发数据包。路由器通过动态维护路由表来反映当前的网络拓扑，并通过网络上其他路由器交换路由和链路信息来维护路由表。
路由器的组成：
RAM（随机存储器）
功能：存放路由表；存放ARP告诉缓存；存放快速交换缓存；存放分组交换缓冲；存放解压后的IOS；路由器加电后，存放running配置文件；
特点：重启或者断电后，RAM中的内容丢失。
NVRAM（非易失性RAM）
功能：存储路由器的startup配置文件；存储路由器的备份。
特点：重启或者断电后内容不丢失。
FLASH（快速闪存）
功能：存放IOS和微代码。
特点：重启或者断电后内容不丢失；可存放多个IOS版本（在容量许可的前提下）；允许软件升级不需替换CPU中的芯片。
ROM(只读存储器)
功能：存放POST诊断所需的指令；存放mini-ios；存放ROM监控模式的代码。
特点：ROM中的软件升级需要更换CPU的芯片（还好这种情况比较少遇到)
CPU（中央处理器）
衡量路由器性能的重要指标，负责路由计算，路由选择等。
背板：
背板能力是一个重要参数，尤其在交换机中。
路由算法：又名选路算法，可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径（即具有最低费用的路径[1] ）。算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准（metric），从而影响到最佳路径的计算。
算法分类：主要有RIP、IGRP（IGRP为 Cisco公司的私有协议）；链路状态路由协议基于图论中非常著名的Dijkstra算法，即最短优先路径（Shortest Path First， SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传 递给在同一区域内的所有路由器。 根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议 （Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域 间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置 选路策略时，具有明显的缺点，已被BGP代替。
OSPF路由算法
OSPF用的是SPF算法，大致上这样，每个路由器已自己为根，计算出到达目的的最短路径树，根据cost计算链路开销，进行选路
有谁能讲下？路由有几种算法？各有什么优缺点？
所有路由算法几乎都可以分类到下面两种算法中。
距离向量算法：
距离向量算法使用Bellman-Ford算法。对于每一条网络上节点间的路径，算法指定一个「成本」给它们。节点会选择一条总成本（经过路径的所有成本总和）最低的路径，用来把资料从节点甲送到节点乙。
此算法非常的简单。当某节点初次启动时，将只知道它的邻居节点（直接连接到该节点的节点）与到该节点的成本。（这些资讯、目的地列表、每个目的地的总成本，以及到某个目的地所必须经过的「下一个节点」，构成路由表，或称距离表。）每个节点定时地将目前所知，到各个目的地的成本的资讯，送给每个邻居节点。邻居节点则检查这些资讯，并跟目前所知的资讯做比较；如果到某个目的地的成本比目前所知的低，则将收到的资讯加入自己的路由表。经过一段时间后，网络上得所有节点将会了解到所有目的地的最佳「下一个节点」与最低的总成本。
当某个节点断线时，每个将它当作某条路径的「下一个节点」的节点会将该路由资讯舍弃，再建立新的路由表资讯。接着，他们将这些资讯告诉所有相邻的节点，再找出到所有可抵达的目的地之新路径。
连线状态算法：
在连线状态算法中，每个节点拥有网络的图谱（一个图）。每个节点将自己可以连接到的其他节点资讯传送到网络上所有的节点，而其他节点接着各自将这个资讯加入到图谱中。每个路由器即可根据这个图谱来决定从自己到其它节点的最佳路径。
完成这个动作的算法——Dijkstra算法——建立另一种资料结构——树。节点产生的树将自己视为根节点，且最后这棵树将会包含了网络中所有其他的节点。一开始，此树只有根节点（节点自己）。接着在树中已有的节点的邻居节点且不存在树中的节点集合中，选取一个成本最低的节点加入此树，直到所有节点都存入树中为止。
这棵树即用来建立路由表、提供最佳的「下一个节点」等，让节点能跟网络中其它节点通讯。
路由算法的比较：
在小型网络中，距离向量路由协定十分简单且有效率，且只需要些微的管理。然而，它们的规模性不好，且 收敛性质也十分差，因此促进了较复杂但规模性较好的连线状态路由协定的开发，以使用在较大型的网络。距离向量路由协定也有无限计数问题（count-to-infinity problem）。
连线状态路由协定的主要优点是在限制的时间内，对于连线改变（例如断线）的反应较快。而且连线状态路由协定在网络上所传送的封包也比距离向量路由协定的封包小。距离向量路由协定必须传送一个节点的整个路由表，但连线状态路由协定的封包只需要传输该节点的邻居节点资讯即可。因此，这些封包小到不会占用可观的网络资源。连线状态路由协定的主要缺点则是比距离向量路由协定需要较多的储存空间与较强的计算能力。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。上面是摘自维基百科的。。百度知道的有个静态路由算法的介绍：链接：。。。希望对你有用
关于路由算法涉及到树和路由算法的特征的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
