分组选路算法

编辑:香料网互动百科 时间:2020-02-21 19:17:55
编辑 锁定
IP协议对分组的处理过程中,最重要的的一个步骤是对目的IP地址的选路,即确定该地址的一跳结点的地址,这个过程中就会用到分组选路算法。
中文名
分组选路算法
目    的
IP分组中对目的IP地址的选路

分组选路算法分类地址系统中的分组选路算法

分类地址系统中的典型分组选路算法如图[1] 

分组选路算法带有子网掩码的分组选路算法

由于在IP的地址分配中引入了子网编址CIDR技术后,分组的选路算法也需要进行相应的调整,为了支持子网编制和CIDR,分类地址系统中直接通过IP地址中的前三位确定地址的类型和网络前缀的长度的方式不再适用。吴类型的IP地址不再是自识别(Self-Identifying)的,仅从IP地址中无法确定网络前缀的长度,因此路由表中除了需要定义网络前缀意外,还需附加定义相应网络的子网掩码。由于子网掩码是可变长的,在选路算法中还需要子网掩码确定目的地址中的网络前缀,以便进行路由查找,改进以后的分组选路算法如图所示。[1] 

分组选路算法混合选路算法

为了支持各种肯能的编制方式(分类地址、子网和CIDR),在实际的Internet中采用的是一种混合的选路算法,以便同时支持各种选路类型。由于存在着多种地址类型(分类的和无类型的)同时存在于路由表中,在进行路由表查询时就不能简单地使用上述两种分组选路算法。这是由于在路由表中有不同类型的地址表项,存在着一个目的IP地址匹配了多个表项的可能性,而这些表项分别指向不同的路由。这种情况经常会发生,因为路由表中可能包含了对同一个网络的一般性的路由藐视和具体的路由描述。[2] 
选路决策时选择,IP协议规定,在搜素路由表示采用最长前缀匹配表项来转发。显然从逻辑上看,使用最长前缀匹配才是最佳的分组选路的处理方式。
最长前缀匹配方式为路由表的搜索带来了一定难度,因为简单的顺序搜索并不能够高效地查找到路由表中的最佳匹配。当前Internet中的路由表都具有相当的规模,例如骨干路由器中路由表项的数量超过10万条,我们需要针对这个问题来设计快速的最长前缀匹配算法。算法的设计既需要考虑搜索的速度,也需要优化存储空间的使用。通常使用的算法是基于二叉树的前缀匹配的优化算法,如Patricia的压缩二叉树(Level Compressed Trie)。
参考资料
  • 1.    ATM网的选路算法  .中国知网[引用日期2015-02-2]
  • 2.    龚向阳等.宽带通信网原理:北京邮电大学出版社,2006年
  • 词条标签:
    中国电子学会