基于RB树和位图混合的网络地址端口转换池管理方法

摘要

本发明公开一种基于RB树和位图混合的网络地址端口转换池管理方法，融合红黑树和位图两种数据结构，实现有效的网络地址端口转换池（NAPT Pool）管理，设置网络地址端口转换池拥有64KB大小的端口资源，每个IP地址对应于一棵RB树；整个RB树初始化为一个根结点；遍历RB树查找具有可分配端口资源的结点；对于每个RB树结点，采用位图的结构储存端口号信息，每个bit位对应于一个端口号。在相应的结点中线性查找256bits位图，直至找到可用的端口号返回；当端口号随机被分配与释放，更新RB树。本发明在接入广域网中虚拟网关服务产品中，可以实现有效的网络地址端口转换，使得在不影响端口地址转换性能的前提下，节省内存资源。

主权项

一种基于RB树和位图混合的网络地址端口转换池管理方法，其中RB树即红黑树，其特征在于，包括以下处理步骤：步骤1：设置NAPT Pool中每个IP地址对应于一棵RB树，一棵RB树占用64Kbits存储空间，每个NAPT Pool拥有64KB大小的端口资源；其中，NAPT Pool即网络地址端口转换池；步骤2：初始化RB树；初始阶段，整个RB树初始化为一个结点，并作为根结点；步骤3：遍历RB树查找具有可分配端口资源的结点；在获取可用端口资源时，所有操作都可以通过RB树遍历，找到可以分配端口资源的结点；步骤4：在RB结点中分配端口号；在RB树中，对于每个RB树结点，采用位图的结构储存端口号信息，每个bit位对应于一个端口号；每个RB树结点管理256个端口，一个256bits位图对应于一个RB树结点；一棵RB树的最大结点数是64KB/256 =256；在相应的结点中线性查找256bits位图，直至找到可用端口；步骤5：当端口号随机被分配与释放，更新RB树。