常见的路由选择算法
一、路由表
所谓路由表，指的是路由器或者其他互联网网络设备上存储的表，该表中存有到达特定网络终端的路径，在某些情况下，还有一些与这些路径相关的度量。
二、常见路由表生成算法
路由算法是提高路由协议功能，尽量减少路由时所带来开销的算法。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。
此外路由算法必须能快速聚合，聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。
（一）静态路由算法
1.Dijkstra算法（最短路径算法）
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。
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的最佳路由。
2.扩散法
事先不需要任何网络信息；路由器把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。 将来会有多个分组的副本到达目的地端，最先到达的，可能是走了“最优”的路径 常见的扩散法是选择性扩散算法。
（二）动态路由算法
1.距离向量路由算法
距离向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法(Ford-FulkersonAlgorithm)，其被距离向量协议作为一个算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量，等等。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。 其优点是算法简单容易实现。缺点是慢收敛问题，路由器的路径变化需要像波浪一样从相邻路由器传播出去，过程缓慢。
每一个相邻路由器发送过来的路由表都要经过以下步骤：1）对地址为X的 路由器发过来的路由表，先修改此路由表中的所有项目：把”下一跳”字段中的地址改为X，并把所有”距离”字段都加1。
2）对修改后的路由表中的每一个项目，进行以下步骤：（1）将X的路由表(修改过的)，与S的路由表的目的网络进行对比。若在X中出现，在S中没出现，则将X路由表中的这一条项目添加到S的路由表中。
（2）对于目的网络在S和X路由表中都有的项目进行下面步骤 ：
（2.1）在S的路由表中，若下一跳地址是x，则直接用X路由表中这条项目替换S路由表中的项目。
（2.2）在S的路由表中，若下一跳地址不是x
，若X路由表项目中的距离d小于S路由表中的距离，则进行更新。
3）若3分钟还没有收到相邻路由器的更新表，则把此相邻路由器记为不可到达路由器，即把距离设置为16。
2.链路状态最短路由优先算法SPF
1）发现邻居结点，并学习它们的网络地址；
2）测量到各邻居节点的延迟或者开销；
3）创建链路状态分组；
4）使用扩散法发布链路状态分组；
5）计算到每个其它路由器的最短路径。
使用Dijkstra算法处理链路信息
四、路由收敛原理
路由收敛:指网络的拓扑结构发生变化后，路由表重新建立到发送再到学习直至稳定，并通告网络中所有相关路由器都得知该变化的过程。也就是网络拓扑变化引起的通过重新计算路由而发现替代路由的行为。
通过路由收敛可以使路由域中所有路由器对当前的网络结构和路由转发达成一致的状态。
收敛时间是指从网络的拓扑结构发生变化到网络中所有路由设备中路由表重新保持一致的状态转换过程。
触发条件
1、路由器失效
2、连接失效
3、管理度量调整等
相关文章：
linux 远程挂载摄像头_基于Linux的嵌入式网络摄像机设计
本嵌入式网络摄像机采用高性能ARM9芯片微处理器，内置嵌入式Web服务器。通过嵌入式多任务操作系统采集摄像机视频数据；采集的视频信号数字化后经MJPEG算法压缩，再通过内部总线送到内置的Web服务器；使用者可以直接用浏览器观看Web服…
2012 ARM嵌入式开发应用研讨会杂谈
记得以前参加的ARM的研讨会，名称是技术研讨会，不知道为什么现在改名为嵌入式开发应用研讨会了。不过今年演讲的重点就是 ARM DS-5开发工具（还免费发放了一本《Linux/Android开发利器 ARM DS-5使用指南》书籍），也许这就…
打印不同对象的字节表示 ( 对int*强制转换成unsigned char*的理解 )
此文章参考《深入理解计算机系统》P31。 先看如下代码： 12345的十六进制表示为：0x00003039 1 #include <stdio.h>2 3 int main()4 {5 int a 12345;6 char *q (char *)(&a);7 for(int i 0; i < sizeof(a); i)8 prin…
NAT技术和代理服务器
一、代理服务器 所谓“代理”，就是代而劳之的意思。代理服务器就是代理网络用户去取得网络信息，形象的说：它是网络信息的中转站，使得一个网络终端和另一个网络终端不直接进行相连，代理网络用户去取得信息。主要工作在O…
链接全局变量再说BSS段的清理
废话就不多说了，开始。。。 再说BSS段的清算 以前遇到一个裸机程序不能改变全局变量值的问题，最后模模糊糊处理了：手动添加了一个链接脚本，清算了BSS段。问题得以处理，就认定是BSS段清算的问题，全局变量在B…
ios启动页尺寸_关于移动端App启动页的策划方案
App启动页是指app在启东时需要加载必要的运行环境和配置，在这个过程中提示用户等待的一个过渡页面。在产品经理眼里启动页是app给予用户重要的第一印象；也是App最重要的黄金页面之一，所有用户100%都会看到的页面。启动页适合用来做以下几个事…
事件流--事件冒泡现象及阻止
事件冒泡现象 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>事件冒泡现象</title><style>div{padding: 50px;}#div1{background: red;}#div2{background: blue;}#div3{background: yell…
谁知道静态成员的纠结心境
我们在实际开发的过程中，可能需要某些类的成员变量并不是针对每一个对象的，而是针对每一个类而言的，比如在银行中有一个利率数据，我们希望的是，当一个利率改变的时候，所有的对象都能够看到这个改变的数据&a…
.net ConfigurationSectionDesigner插件使用
最近接触了vs2010的一款插件：ConfigurationSectionDesigner。ConfigurationSectionDesigner是一个图型化设计.net的配置块和自动生成需要代码和schema定义的codeplex上的一个开源项目，现在分享出来，希望对大家有所帮助。 .Net配置体系中可以是…
对应到对象 数据库驼峰_【GI的自主空间数据库】一种竞争力，叫技术引领；一种竞争力，叫时间沉淀...
引子：GI的自主空间数据库及GIS框架来自于求学时MAPGIS的引导，工作时ARCGIS的追随，读博时IBM和Microsoft2篇文献...。即使在大数据技术发展的今天，自主空间数据库存储仍然有其技术优势，近20年的时间沉淀，是G…
TSM备份Windows数据
一、备份数据 1.使用备份勾当客户端，可以在原始文件出现损坏的时候，恢复备份版本。TSM提供备份和恢复文档的类型包括:FAT，NTFS和FAT32.2.合适备份和合适归档文件当备份-归档客户端备份或归档一个文件，他会发送一份文档的副本和它的…
GM Tech 2 works with Hummer Yes or No
This is about GM Tech 2 scan tool for Hummer troubleshooting and programming. Can I have a cheap Tech 2 for Hummer? Yep. Both the original and HQ clone can work for your car. Where can I get a working clone at a good price? https://www.obd2tool.com/goods…
程序的编译和链接过程
一.虚拟机、linux简介简单介绍一下虚拟机还有就是各种操作系统，比如centos，Ubuntu操作系统：linux（centos、Ubuntu、redhat），Android，Windows（xp、win8、win10）进程&#…
Nosql网络阅读
#1 Node.jsmongodb 开源项目 https://github.com/DoubleSpout/wujb 作者博客:http://snoopyxdy.blog.163.com/blog/static/60117440201261844125973/ #1 关系数据库还是NoSQL数据库 NoSQL的分类 NoSQL仅仅是一个概念，NoSQL数据库根据数据的存储模型和特点分为很多…
python 文案自动生成_Python自动化测试如何自动生成测试用例？
原文作者：陈安妮annie1原出处：简书上文内容不用于商业目的，如涉及知识产权问题，请权利人联系博为峰，我们将立即处理。传统的测试用例需要测试或者开发人员将用户的操作用代码表示出来，通过断言判断是否和预…
Linux下图解minicom安装
Linux下图解minicom安装 minicom是一个串口通信工具，就像Windows下的HyperTerminal。可用来与串口设备通信，如调试交换机和Modem等。它的Ubuntu软件包的名称就叫minicom，用apt-get install minicom即可安装。全文见附件pdf
【C#技术】一篇文章搞掂：Infragistics组件库
工具栏 // 按钮不可按 tool.SharedProps.Enabled false; Grid // Grid中记录时间 // 建议SQL Server中使用字符字段（没有深入测试，只是字符字段可行），然后设置Grid的属性中，列的Style属性为Time或TimeWithSpin// 使用…
移动端开发小结
1. viewport viewport：除去所有工具栏、状态栏、滚动条等之后用于查看网页的区域，打个比方，现在有一张报纸摆在你面前，但是这张报纸被一本书压住了，所以你只能看到报纸的一部分，这部分可以查看到的区域就是…
vim编辑文章后不能修改
我们在使用vim打开一个文件的时候，经常会弹出下面的界面 为什么会出现这个界面呢 用vim编辑文件(如这里的test.txt)时,系统会自动产生一个文件叫.test.txt.swp.如果正常退出,此文件会被自动删去.如果上次非正常退出,如果再编辑它,系统会首先查.test.txt.swp 是否存…
echart x轴标签偏移_移动端H5页面滑动手势X轴实例
话不多少，上代码。let touchX 0 // 默认初始值// 两行注释伪代码，绑定 touchstart 与 touchend 事件// dom.addEvenetListener(touchstart, touchStart)// dom.addEvenetListener(touchend, touchEnd)function touchStart(e) { // 手指触碰时候…
读书笔记(2) OpenLayers中的图层
OpenLayers有多个不同的图层类，每一个都可以连接到不同的地图服务器。例如通过Layer.WMS类可以连接到WMS地图服务器，通过Layer.Google类可以连接到谷歌地图服务器。OpenLayers中的每个图层都是独立的，对一个的操作不会影响到另外一个。 不管地…
自定义WPF窗体形状
介绍 你好WPF爱好者。 随着WPF等统一API语言的发明，丰富用户界面变得非常容易。 创建丰富的用户界面只是一个想法。 您需要拥有的是创造性思维和最新技术融合。 WPF和Expression Blend在制作丰富的UI应用程序，清晰的图形和非常好的动画方面非常有用。 背…
与jQuery的感情碰撞——由浅入深学jQuery
原来的时候自己看过jQuery，但是对于什么是jQuery，除了知道jQuery是一种javascript类库外，除了会用几个网页特效外，其他的我这真的是不知道啊。眼看自己就要找工作了，所以自己需要好好学习一下，系统的了解一…
线程互斥和同步-- 互斥锁
一. 线程分离我们一般创建的线程是可结合的，这个时候如果我们调用pthread_jion()去等待的话，这种等待的方式是阻塞式等待，如果主线程一直等待，主线程就无法做其他的事情了，所以应该使用线程分离，让子线程由…
calipso是什么意思_眰恦是什么意思？
展开全部眰恦作为一个不常见到的词，其实出自一本同名小说的书名。眰恦读作zh shng ，在书中62616964757a686964616fe59b9ee7ad9431333433656665的意思就是，目光所至，心之所向，皆是你。眰，单字意思是视&#…
一个mongosee例子
var express require(express),mongoose require(mongoose); //引入mongoose模块 //连接mongodb数据库 nodejs为数据库名称 mongoose.connect(mongodb://localhost/nodejs);//获取Schema 以及 ObjectId 对象 var Schema mongoose.Schema,ObjectId Schema.ObjectId;//创建一…
mongoDB入门
**使用了不存在的对象，即创建该对象use db 使用db数据库 show dbs 查看当前服务器中写在磁盘上的数据库 show tables 查看数据库中的collection db 查看当前使用的数据库1.增删改查： 增：db.collection.insert({数据}) 自动生成 _id : ObjectI…
哈希--直接定值法和除留取余法
1. 哈希是一种算法，哈希表是用哈希算法构造出来的一种数据结构2. 哈希算方法的几种方法直接定值法 这里有一个例题，就是我们想判断某一字符串中，某一个字符出现的个数，我们可以使用哈希的思想，就是可以遍历一遍字符串&…
两条波浪线符号_四年级数学上册第二单元“线的认识”作业单（附带答案）
“线的认识”作业单一、线段、射线和直线。1.“线段、射线和直线”之间的联系与区别。名称形状长度端点关系2.表示方法：分别画出一条线段、射线和直线，并用字母进行表示。3.概念： (1) (2) (3) 二、相交与垂直1.概念：(1) (2)表示方…
CTime类小结1
参考：http://www.cnblogs.com/chuncn/archive/2009/03/12/1409261.html CTime类1．构造和初始化CTime类对象CTime类有下列构造函数：CTime（ ）;CTime（ const CTime& timeSrc ）;CTime࿰…