文档介绍：袄路由算法及分类袃路由算法及分类:蒁羇1、非自适应算法,静态路由算法芅不能根据网络流量和拓扑结构的变化更新路由表,使用静态路由表,也称为固定式路由选择算法。莁特点:简单,开销少;灵活性差。芀2、自适应算法,动态路由算法肆可根据网络流量和拓扑结构的变化更新路由表。蚆特点:开销大;健壮性和灵活性好。肃3、最优化原则(optimalityprinciple)聿如果路由器J在路由器I到K的最优路由上,那么从J到K的最优路由会落在同一路由上。膆4、汇集树(sinktree)肇从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树,称为汇集树;薁路由算法的目的是找出并使用汇集树。肂芆几种典型的路由选择算法:膄芃1、最短路径路由算法(ShortestPathRouting)袁1)基本思想芆构建子网的拓扑图,图中的每个结点代表一个路由器,每条弧代表一条通信线路。为了选择两个路由器间的路由,算法在图中找出最短路径。薅2)测量路径长度的方法羄结点数量薀地理距离莆传输延迟羆距离、信道带宽等参数的加权函数莂3)Dijkstra算法莈每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临时性标注和永久性标注;蒆初始时,所有结点都为临时性标注,标注为无穷大;莆将源结点标注为0,且为永久性标注,并令其为工作结点;膄检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注,则用新计算得到的和重新标注该结点;莁在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并成为下一轮检查的工作结点;薆重复第四、五步,直到目的结点成为工作结点;蒃薂2、洪泛及选择洪泛算法膀1)洪泛算法(Flooding)蚅属于静态路由算法袄a)基本思想芄把收到的每一个包,向除了该包到来的线路外的所有输出线路发送。罿b)主要问题罿洪泛要产生大量重复包。芅c)解决措施螂每个包头包含站点计数器,每经过一站计数器减1,为0时则丢弃该包;羂记录包经过的路径聿2)选择性洪泛算法(selectiveflooding)蚆洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。蒄3)应用情况螁路由器和线路的资源过于浪费,实际很少直接采用;腿具有极好的健壮性,可用于军事应用;肇作为衡量标准评价其它路由算法。羂3、基于流量的路由算法(Flow-BasedRouting)薀属于静态路由算法艿1)基本思想芄既考虑拓扑结构,又兼顾网络负荷;蚃前提:每对结点间平均数据流是相对稳定和可预测的;艿根据网络带宽和平均流量,可得出平均包延迟,因此路由选择问题归结为找产生网络最小延迟的路由选择算法。荿提前离线(off-line)计算蚄2)需要预知的信息肁网络拓扑结构;莁通信量矩阵Fij;葿线路带宽矩阵Cij;肅3)路由算法(可能是临时的)螃肀葿1/m=800bits蒆根据排队论,平均延迟T=1/(mC-l)芁衿4、距离向量路由算法(DistanceVectorRouting)蕿属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法,,被RIP协议采用。薃1)基本思想羃每个路由器维护一张表,表中给出了到每个目的地的已知最佳距离和线路,并通过与相邻路由器交换距离信息来更新表;蚈以子网中其它路由器为表的索引,表项包括两部分:到达目的结点的最佳输出线路,和到达目的结点所需时间或距离;蚈每隔一段时间,路由器向所有邻居结点发送它到每个目的结点的距离表,同时它也接收每个邻居结点发来的距离表;羄邻居结点X发来的表中,X到路由器i的距离为Xi,本路由器到X的距离为m,则路由器经过X到i的距离为Xi+m。根据不同邻居发来的信息,计算Xi+m,并取最小值,更新本路由器的路由表;蒁注意:本路由器中的老路由表在计算中不被使用蚁螈2)无限计算问题莅算法的缺陷:对好消息反应迅速,对坏消息反应迟钝;膃蒀3)水平分裂算法袈工作过程与距离向量算法相同,区别在于到X的距离不向真正通向X的邻居结点报告,使得坏消息传播的也快。螆虽然广泛使用,但有时候会失败。薁腿5、链路状态路由算法(LinkStateRouting)羈1)距离向量路由算法的主要问题***选择路由时,没有考虑线路带宽;莂路由收敛速度慢。节2)链路状态路由算法肈发现邻居结点,并学****它们的网络地址;莃路由器启动后,通过发送HELLO包发现邻居结点;肄两个或多个路由器连在一个LAN时,引入人工结点;羀测量到每个邻居结点的延迟或开销;肈一种直接的方法是:发送一个要对方立即响应的ECHO包,来回时间除以2即为延迟。螄将所有学****到的内容封装成一个包;蒂包以发送方的标识符开头,后面是序号、年龄和一个邻居结点列表;蝿列表中对应每个邻居结点,都有发送方到它们的延迟或开销;-15膈链路状态包定期创建