路由算法基本概念-盛世时代

来源:盛世时代 时间:2017-05-06
  路由算法是网络层软件的一部分,它负责确定一个进来的分组应该被传送到哪一条输出线路上。如果子网内部使用了数据报,那么路由器必须针对每一个到达的数据分组重新选择路径,因为从上一次选择了路径之后,最佳的路径可能已经改变了。如果子网内部使用了虚电路,那么只有当一个新的虚电路被建立起来的时候,才需要确定路由路径。因此,数据分组只要沿着已经建立的路径向前传递就行了。无论是针对每个分组独立地选择路由路径,还是只有建立新连接的时候才选择路由路径,一个路由算法应具各的特性有:正确性、简单性、健壮性、稳定性、公平性和最优性。
  路由算法可以分为:非自适应的和自适应的。非自适应算法不会根据当前测量或者估计的流量和拓扑结构来调整它们的路由决策,这个过程也称为静态路由。相反,自适应算法则会改变它们的路由决策,以反映出拓扑结构的变化,通常也会反映出流量的变化情况,这个过程称为动态路由。
   (1)图的定义
  所谓图G是一个三元组,记作G=〈V(G),E(G),φ(G)),其中:
   V(G)=(v1,v2,…,vn),V(G)=Φ,称为图G的节点集合。
  E(G)=(e1,e2,…,en)是G的边集合,其中ei:为{vj,vt)或(vj,vt〉。若ei为(vj,vt),称ei为 vj和vt为端点的无向边;若ei为〈vi,vt〉,称色为以vj为起点,vt为终点的有向边。
  φ(G):E→V×V称为关联函数。
  (2)无向图
  每一条边都是无向边的图称为无向图。
  (3)有向图
  每一条边都是有向边的图称为有向图。
  (4)图的顶点度
  设G是任意图,x为G的任一节点,与节点x关联的边数称为x的度数。记作deg(x)。射入x的边数称为宽的入度 ,记作deg+(x);射出∝的边数称为贸的出度,记作deg-(x).
  (5)连通图
  在无向图G中,如果从顶点x到顶点y有路径,则称x和y是连通的。如果对于图中任意两个顶点都是连通的,则称G是连通图。
  (6)带权图
  有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数称为杈,带权的图称为带权图。
  (7)树
  无圈连通无向图,树中度数为1的节点称为树的叶,树中度数大于1的节点称为树的分支点或内点。不相交的若干树称为森林。
  (8)生成树
  如果T是G的一个生成子图而且又是一稞树,则T是图G的一颗生成树。
  (9)最小生成树
  连通加杈图里杈和最小的生成树称为最小生成树。
    路由算法在路由协议中起着至关重要的作用,采用何种算法往往决定了最终的寻径结果,因此选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标:
  (1)最优化:指路由算法选择最佳路径的能力。
  (2)简洁性:算法设计简洁,利用最少的软件和开销,提供最有效的功能。
  (3)坚固性:路由算法处于非正常或不可预料的环境时,如硬件故障、负载过高或工作失误时,都能正确运行。由于路由器分布在网络联接点上,所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验,并在各种网络环境下被证实是可靠的。
  (4)快速收敛:收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时,路由器就发出更新信息。路由更新信息遍及整个网络,引发重新计算最佳路径,最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。
  (5)灵活性:路由算法可以快速、准确地适应各种网络环境。例如,某个网段发生故障,路由算法要能很快发现故障,并为使用该网段的所有路由选择另一条最佳路径。
  路由算法按照种类可分为以下几种:静态和动态、单路和多路、平等和分级、源路由和透明路由、域内和域间、链路状态和距离向量。前面几种的特点与字面意思基本一致,下面着重介绍链路状态和距离向量算法。
  链路状态算法(也称最短路径算法)发送路由信息到互联网上所有的结点,然而对于每个路由器,仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量算法(也称为Bellman-Ford算法)则要求每个路由器发送其路由表全部或部分信息,但仅发送到邻近结点上。从本质上来说,链路状态算法将少量更新信息发送至网络各处,而距离向量算法发送大量更新信息至邻接路由器。
  由于链路状态算法收敛更快,因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面,链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间,因此链路状态算法将会在实现时显得更昂贵一些。除了这些区别,两种算法在大多数环境下都能很好地运行。
  最后需要指出的是,路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由,通过一定的加权运算,将它们合并为单个的复合度量、再填入路由表中,作为寻径的标准。通常所使用的度量有:路径长度、可靠性、时延、带宽、负载、通信成本等。
上一篇:AB类放大器-盛世时代 下一篇:功率放大器种类-功率放大电路的分类-盛世时代

在线沟通