路由表更新计算
当您想要了解更多有关路由表更新计算和路由表更新机制的知识时,本文将为您提供全面的介绍和解释。如果本文对您有所帮助,不要忘记与您的朋友分享并收藏本站。
本文目录一览:
简述ospf的路由计算过程。
在OSPF网络,路由的计算不是简单的把源地址与目的地址进行关联这么简单,需要考虑到许多因素,以确定一条***路径。整个OSPF路由计算过程可分为:邻接关系建立→DR/BDR选举→发送LSA→创建路由表→维护路由表这五大基本步骤。具体描述如下:
(1)建立邻接关系。
所谓"邻接关系"(Adjacency)是指OSPF路由器以交换路由信息为目的,在所选择的相邻路由器之间建立的一种关系。在OSPF中,邻居(Neighbor)和邻接(Adjacency)是两个不同的概念。OSPF路由器启动后,便会通过OSPF接口定期(默认为10秒)向外发送Hello报文。收到Hello报文的OSPF路由器会检查报文中所定义的参数,如果双方一致就会形成邻居关系。但形成邻居关系的双方不一定都能形成邻接关系,这要根据网络类型而定。只有当双方成功交换DD(Database Description,数据库描述)报文,交换LSA并达到LSDB的同步之后,才形成真正意义上的邻接关系。如果在设定的期限(默认为40秒)内没有收到某OSPF路由器发来的Hello报文,则认为该OSPF路由器无效。
具体步骤是:路由器首先发送拥有自身ID信息(Loopback端口或***的IP地址)的Hello报文。与之相邻的路由器如果收到这个Hello报文,就将这个报文内的ID信息加入到自己的Hello报文内。然后在后面发送的Hello报文中就包括了原来所接收到的邻居路由器的ID信息。如果路由器的某端口收到从其他路由器发送的含有自身ID信息的Hello报文,则它根据该端口所在网络类型确定是否可以与对端路由器建立邻接关系。
在点对点网络中,路由器将直接和对端路由器建立起邻接关系,并且该路由器将直接进入到下面的第(3)操作,发送LSA以发现其他路由器;若为多路访问网络, 则该路由器将进入下面第(2)步的DR/BDR选举。
(2)选举DR/BDR。
在广播或者多路访问OSPF网络中,各相邻路由器都建立了相邻关系后,就要选举一个担当区域内的LSU通告代理角色的DR(指定路由器)和BDR(备份指定路由器),因为在OSPF网络中,为了减少LSU通告的流量,各路由器之间不直接发送链路状态信息,而是通过选举DR/BDR进行统一分发的。其他路由器要发送LSU,则先把LSU发给DR/BDR,再由DR或者BDR(只有在DR失效时才使用它)在组播给所有非DR,或者BDR的路由器。
DR和BDR是由同一网段中所有的路由器根据路由器优先级、Router ID通过Hello报文选举出来的,只有优先级大于0的路由器才具有选举资格。具体的选举过程如下:
①在与一个或多个邻居之间的双向通信建立起来之后,本地路由器对每个邻居发送来的Hello包中的优先级、DR和BDR域进行检查。此时所有路由器都宣称自己为DR(将它们自己的接口地址置于Hello包的DR域中);而且所有路由器都宣称自己为BDR(将它们自己的接口地址置于Hello包的BDR域中)。
②如果一或多个备选路由器将它(们)自身的接口地址置于DR域中,拥有***优先级的邻居将被宣告为DR。如果路由器优先级一样,拥有***Router ID的邻居将被选举出来。
③然后再将自身的接口地址置于BDR域中的路由器中选择拥有***优先级的路由器作为BDR。如果这些宣称自己为BDR路由器的优先级相等,则拥有***Router ID的邻居将被选举作为BDR。
④如果没有任何路由器被宣告为BDR,拥有***优先级的非DR邻居路由器将被宣告为BDR;如果多个优先级相同的这样的路由器,则拥有***Router ID的邻居将被选举作为BDR。
(3)发送LSA。
作为一种典型的链路状态的路由协议,OSPF还得遵循链路状态路由协议的统一算法。当路由器初始化或当网络结构发生变化(例如增减路由器、链路状态发生变化等)时,路由器会产生链路状态广播数据包LSA,该数据包里包含路由器上所有相连链路,也即为所有端口的状态信息。所有路由器会通过泛洪方式来交换链路状态数据。
在这个步骤中,路由器与路由器之间首先利用Hello报文的ID信息确认主从关系,然后主从路由器相互交换部分链路状态信息。每个路由器对信息进行分析比较,如果收到的信息有新的内容,路由器将要求对方发送完整的链路状态信息。这个状态完成后,路由器之间建立完全邻接关系,同时各邻接路由器拥有自己独立的、完整的链路状态数据库。
在多路访问网络内,DR与BDR互换信息,并同时与本子网内其他路由器交换链路状态信息。在Point-to-Point(点对点)或Point-to-MultiPoint(点对多点)网络中,相邻路由器之间会直接交换链路状态信息。
(4)创建路由表。
当网络重新稳定下来,也可以说OSPF路由协议收敛下来时,所有的路由器会根据其各自的链路状态信息数据库,采用SPF(最短路径优先)算法计算并创建路由表。OSPF路由器依据链路状态数据库的内容,独立地用SPF算法计算出到每一个目的网络的路径,并将路径存入路由表中。该路由表中包含路由器到每一个可到达目的地的开销以及到达该目的地所要转发的下一个路由器(next-hop)。
OSPF利用开销来计算路由路径性能的,开销最小者即为最短路径。在配置OSPF路由器时可根据实际情况,如链路带宽、时延等设置链路的开销大小;开销越小,则该链路被选为路由的可能性越大。这里的开销是根据链路类型来计算的,不同的链路类型对应的开销值不一样。
(5)维护路由信息。
当链路状态发生变化时,OSPF通过泛洪过程广播网络上的其他路由器。OSPF路由器接收到包含有新信息的链路状态更新报文,将更新自己的链路状态数据库,然后用SPF算法重新计算路由表。在重新计算过程中,路由器继续使用旧路由表,直到SPF完成新的路由表计算。新的链路状态信息将发送给其他路由器。值得注意的是,即使链路状态没有发生改变,OSPF路由信息也会自动更新,默认时间为30分钟。
更新后的路由表(求解计算过程和答案)
答:收到路由向量A(0,3,12,16)B(15,0,4,6)
C更新后的路由表(分别到A,B,C,D的路由向量)
(7,A),(10,A),(0,-),(20,B)
路由算法
路由算法是网络层软件的一部分。子网提供数据报服务,每个包都要做路由选择;子网提供虚电路服务,只需在建立连接时做一次路由选择
正确性,简单性,健壮性(鲁棒性,网络出现意外情况时候的解决问题的能力。例如突然某个路由器停电了,使得周边的路由器都没法正常工作,如果出现这样的问题说明路由器的健壮性不够),稳定性(常规使用是否稳定,数据量增多的时候能否正常工作),公平性(网络资源的使用是否公平,避免有些节点出现特别繁忙的状态,而有些节点总是处于很闲的状态),最优性
• 按转发方式和数据副本数量划分
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,直到年龄比新到的包小,接下来就可以正常接包了。不过这之前到的包都会被丢弃,这也是没有办法的事
• 链路状态包到达后,延迟一段时间,并与其它已到达的来自同一路由器的链路状态包比较序号,丢弃重复包,保留新包
• 链路状态包需要应答
为了保证数据传输的可靠性
现在,你已经了解了如何设置你的路由器和Wi-Fi,并开始享受无线上网的便利。但是,请记得保护你的网络安全,使用强密码并定期更改密码,以保护你的隐私和数据安全。