通信交换技术知识点精讲之路由选择算法

       >>>>>点击进入了解通信工程师网络课堂

       >>>>>点击进入了解通信工程师培训视频

       >>>>>点击进入了解通信工程师面授班

       下面是由希赛小编提供的通信交换技术知识点精讲之路由选择算法，希望对学友们有所帮助。具体内容如下：

       路由选择算法

       (1)用图表示网络

       路由问题就是解决分组交换网中的各节点交换机应该如何进行分组转发的问题.因此有必要先研究网络的拓扑结构。可以用图论中的“图”（Graph)来表示一个分组交换网络，用图的“顶点”表示网络节点，用连接顶点的“边”表示网络节点间的链路，如一个网络图G表示为G=(V,E),其中，F是网络节点的集合，E是链路的集合。

       通过网络的一条有向通路（Path),可用一组链路的有序集（L1,L2,……，Ln）来表示。在分组交换网络中，该通路称为“分组传送路径”（Route)。因此，所谓“路由算法”或“路径选择算法”，就是指确定分组从它的源点到达目的点的有向传输通路的法则。

       现在面临的问题是：

       ①采用什么算法来选择合适的路径？

       ②依据什么信息来进行这种选择？

       ③应该如何执行这种选择的策略？

       ④用什么标准来评判所选择路径的好坏？

       下面就讨论路由选择的一般原理以及几种不同的路由选择策略和算法。理想的路由选择算法图5-16网络

       一个理想的路由选择算法应满足如下要求。

       ①算法必须是正确的和完整的。每一个节点交换机中的路由表，都必须给出到所有可能的目的节点的下一节点，并且沿着各交换机中路由表所指引的路由，分组一定能够最终到达目的计算机所在的那个节点交换机，并且该交换机可以根据自己的路由表识别出目的计算机直接与自己相连，因此不会再向其他交换机转发该分组。

       ②算法在计算上应尽可能简单。对于数据报分组交换方式，在每个节点上都要对每个分组进行路由选择的计算，路由的计算必然增加分组的转发处理时延，因此应简化计箅。另外，路由选择的计算不应使网络通信资源增加太多的额外开销。若为了计算合适的路由必须使用网络其他节点发来的大量状态信息，就会加大额外开销。

       ③算法应能适应分组流量和网络拓扑的变化，也就是说，要有自适应性。当网络中某些链路的流量过大时，算法应能自适应地改变路由，以均衡各链路的负载。当某个或某些节点、链路发生故障不能工作，或者修理好了再投人运行时，算法能及时地改变路由。有时称这种自适应性为“顽健性”（Robustness)。

       ④箅法应具有稳定性。在网络通信流童和网络拓扑相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应产生过多的振荡。所谓振荡，是指由算法得出的路由在一些路由之间来回不停地变化。

       ⑤算法应是公平的。这就是说，算法应对所有用户（除对少数优先级髙的用户）都是平等的。例如，若使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显地不符合公平性的要求。

       ⑥算法应是最佳的。这里的“最佳”是指以最低的“代价"（Cost)来实现的路由算法。这里特别需要注意的是，在研究路由选择时，“代价”并#一定指“钱”。通常是给每一条链路指定一定的代价，而这个代价又是由一个或多个因素（几个因素综合起来）决定的，如链路长度、数据率、链路容量、是否要保密、传输时延等，甚至还可以是一天中某一个小时内的通信流量、节点缓冲区被占用的程度、链路的差错率情况等。可以根据用户的具体情况来设置每一条链路的“代价”。从这里坷以看出，不存在一种绝对的最佳路由算法。所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

       一个实际的路由选择算法，应尽可能接近理想的算法。在不同的应用条件下，对以上提出的六个方面也可有不同的侧重。

       2.路由策略的分类

       路由选择算沬是解决如何根据网络拓扑和状态，按照一定的性能准则，计算分组传送路径的问题。而路由策略则是解决路由的选择能否适应网络拓扑和状态变化的问题。这两者不可混淆。一般说来，路由选择算法仅是路由策略的一部分。倘若从路由的选择能否随网络的变化而自适应地进行调整变化来区分，则路由策略可分为两大类，即非自适应路由选择策略与自适应路由选择策略。

       非自适应路由选择也叫做静态路由选择，其特点是简单和开销较小，但不能及时适应网络状态（包括网络拓扑和流量分布）的变化。自适应路由选择也叫做动态路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂。下面两小节将分别进行介绍。

       返回目录：通信交换技术知识点精讲之路由法汇总

       相关推荐：

 中级通信工程师交换技术考试真题汇总

       中级通信交换技术知识点精讲之交换网络汇总

   中级通信工程师交换技术考试培训视频推荐