一种路由表项的快速存储方法

摘要

本发明提供一种路由表项的快速存储方法，采用256tire树结构来配置路由表项，该256tire树的树高为四，四个节点均包括索引值为0～255的256个索引表项，根节点的索引值为255的索引表项直接指向的路由表项表示默认路由；而第二级节点的索引值为255的索引表项指向的是匹配中根节点后，第二级节点都没有匹配的情况下，应该返回的路由表项；第三级节点的索引值为255的索引表项指向的是匹配中前两级节点后，第三级节点都没有匹配中的情况下，应该返回的路由表项；第四级节点的索引值为255的索引表项指向的是匹配中前三级节点后，第四级节点都没有匹配中的情况下，应该返回的路由表项。本发明不仅路由查找都会很快速，提高了路由查找的效率，从而提高路由器的转发性能，还能节省内存空间。

主权项

一种路由表项的快速存储方法，其特征在于：采用256trie树结构来配置路由表项，该256trie树的树高为四，即包括根节点、第二级节点，第三级节点，第四级节点，所述根节点、第二级节点，第三级节点，第四级节点均包括索引值为0～255的256个索引表项，所述根节点的索引值为255的索引表项直接指向的路由表项表示默认路由；而第二级节点的索引值为255的索引表项指向的是匹配中根节点后，第二级节点都没有匹配的情况下，应该返回的路由表项；第三级节点的索引值为255的索引表项指向的是匹配中前两级节点后，第三级节点都没有匹配中的情况下，应该返回的路由表项；第四级节点的索引值为255的索引表项指向的是匹配中前三级节点后，第四级节点都没有匹配中的情况下，应该返回的路由表项；将任意一个目的ip地址，都用4个一字节的数值表示；该4个一字节的数值分别称为ip地址的第一字节，第二字节，第三字节和第四字节；所述路由表项的快速存储方法包括256trie树生成的过程，该256trie树生成的过程包括下述步骤：步骤(1)、判断配置的路由表项的类型：a、如果配置的是默认路由，则直接把根节点的索引值为255的索引表项指向该默认路由表项，无需进入步骤(2)；b、如果是掩码长度小于等于8的路由表项，需要设置到根节点，所有索引值和目的ip地址前缀匹配的，且前缀匹配长度为掩码长度的索引表项都要设置路由表项；设置路由表项的过程按步骤(2)进行；c、如果是掩码长度大于8小于等于16的路由表项，先取目的ip的第一字节，算出根节点的索引值，然后取出目的ip地址的第二字节，找到和第二字节前缀匹配，并且匹配长度是掩码减8的所有第二级节点的索引表项，这些第二级节点的索引表项和刚才算出的索引值对应的索引表项建立关联，同时按步骤(2)设置这个路由表项；d、如果是掩码长度大于16小于等于24的路由表项，先取目的ip地址的前两字节，算出根节点的索引值和第二级的索引值，该根节点的索引值和第二级的索引值分别等于目的ip地址的第一字节，第二字节的值，把根节点中与根节点的索引值对应的索引表项关联到第二级节点，把第二级节点中与第二级的索引值对应的索引表项关联到第三级节点，然后，取出目的ip地址的第三字节，找到和第三字节前缀匹配，并且长度是掩码长度减16的所有第三级节点的索引表项，这些第三级节点的索引表项，和所述与第二级的索引值对应的索引表项建立关联，同时按步骤(2)设置路由表项；e、如果掩码长度大于24小于等于32的路由表项，先取目的ip地址的前三字节，算出根节点的索引值、第二级的索引值和第三级的索引值，该根节点的索引值、第二级的索引值和第三级的索引值分别等于目的ip地址的第一字节，第二字节的值、第三字节的值，把根节点中与根节点的索引值对应的索引表项关联到第二级节点，把第二级节点中与第二级的索引值对应的索引表项关联到第三级节点，把第三级节点中与第三级的索引值对应的索引表项关联到第四级节点，然后，取出目的ip地址的第四字节，找到和第四字节前缀匹配，并且长度是掩码长度减24的所有第四级索引表项，这些第四级索引表项和所述的第三级的索引值对应的索引表项建立关联，同时按步骤(2)设置路由表项；步骤(2)、设置路由表项：对于前三级节点，除了默认路由以外，要关联路由表项，上一级节点都是和下一级节点的索引值为255的索引表项建立关联，然后将该索引的索引值为255的索引表项指向这个路由表项；第四级节点表项则是直接指向步骤(1)对应的所述路由表项；在设置路由表项时要先看是否已经关联了路由表项了，如果该索引表项已经指向了一个路由表项，则比较这两个路由表项中掩码长度，该索引表项与掩码长度长的那个路由表项关联；如果上一级节点要关联的下一级节点没有创建，则需要先创建下一级节点。