对路由表进行空间管理的方法、装置、交换机及路由器

摘要

本发明涉及一种对路由表进行空间管理的方法、装置、交换机及路由器，通过空间管理链表中的空间管理单元对路由表空间进行分配管理，使得三层交换机或路由器插入路由表中的表项依照掩码(前缀)长度由长至短的顺序进行排列，保证了最长前缀匹配一开始便可匹配到最长的掩码长度路由表项，避免了同一表项在路由表中的重复存放，以及对路由表中的所有表项进行匹配后才能获得最长的掩码长度路由表项，大大提高了路由表查找速度；同时路由表中的表项按照一定顺序排列也有利于表项的快速插入和删除，大大提高了路由表的空间利用率。

主权项

一种对路由表进行空间管理的方法，其特征在于，包括：计算待插入表项的掩码长度；遍历空间管理链表中的空间管理单元；所述空间管理链表中，各空间管理单元与掩码长度一一对应，管理与对应的掩码长度相同的路由表中表项；所述各空间管理单元按照对应的掩码长度从长到短的顺序排列，均设置有表项在所述路由表中存储的开始地址start、表项在所述路由表中存储的结束地址end、前一个空间管理单元存储对应的掩码长度prev、后一个空间管理单元对应的掩码长度next、本空间管理单元在所述路由表中管理的掩码长度对应的空间存储的表项个数vent及本空间管理单元在所述路由表中管理的掩码长度对应的空间中的空闲空间fent；获取与所述待插入表项的掩码长度对应的空间管理单元，确定所述待插入表项在路由表中的存放位置，插入所述待插入表项。