一种基于两级双向哈希链表的IP数据流管理方法

摘要

本发明公开了一种基于两级双向哈希链表的IP数据流管理方法，通过构建IP数据流的状态信息和两级双向哈希链表，对于网络中任意到达的IP数据流，实时更新该两级双向哈希链表，并每经过一个测量周期，导出两级双向哈希链表中的IP数据流的状态信息。实现了在高速网络中对IP数据流管理的准确性和实时性，还能够兼容TCP数据流和UDP数据流，具有很强的扩展性。

说明书

技术领域

本发明涉及计算机网络领域，尤其涉及一种基于两级双向哈希链 表的IP数据流管理方法。

背景技术

在网络规模和用户数量不断膨胀、业务环境日趋复杂的背景之 下，加强IP数据流管理，对于从整体上把握网络业务以及用户行为 特征而言具有极其重要的意义。

IP数据流管理主要是指通过捕获流经网络节点或者链路的数据 分组，对所得IP数据流进行统计、分析、处理，实时提取出反映网 络特性的流量统计特征，进而获知网络流量在不同特征维度上的构 成，保证网络的健康运行。它是进行网络故障与异常检测、网络业 务预测、网络管理与规划、以及网络服务质量(QoS)管理的前提和 基础。

然而，以各种不同应用为驱动，互联网正朝着高速化和宽带化 的方向发展：一方面，骨干链路上并发数据流的数量巨大，常常超 过百万；另一方面，骨干链路数据率已从2.5Gbps提升到10Gbps、 40Gbps甚至更高，导致报文到达时间大大缩短，如在40Gbps高速链 路上，假设平均数据包长为1000bits，则为了达到线速处理，所能允 许的每个数据包的处理时间平均为25ns。因此，高速网络环境对IP 数据流的管理方法提出了更高的实时性要求。

另外，传统IP数据流管理方法多采用一级单向链表方法，若网 络中出现大规模的DDoS攻击，会导致大量短数据流将长数据流挤出 缓存的现象，使得一部分长数据流被误删，降低了IP数据流管理的 准确性。

再者，传统的IP数据流管理方法主要是通过删除内存中已完成 传输的数据流表项，来实现海量信息的存储需求。例如，TCP数据 流通过FIN/RST结束包，来标识该类型数据的流表项的结束，而UDP 数据流无结束包，无法判断该种类型数据流的结束与否。

为此，需要针对高速网络环境，降低IP数据流处理时延，提高 对IP数据流管理的实时性，同时还需要保证IP数据流管理的准确性， 能够兼容对TCP数据流和UDP数据流进行维护和管理。

发明内容

本发明主要解决的技术问题是提供一种基于两级双向哈希链表 的IP数据流管理方法，解决现有技术中在高速网络环境中IP数据流 管理的实时性和准确性不足的问题。

为解决上述技术问题，本发明采用的一个技术方案是：提供一种 基于两级双向哈希链表的IP数据流管理方法，该方法包括：第一步， 构建IP数据流状态信息，该状态信息包括：标识域、长度域、时间 域、和/或TCP比特域；第二步，构建用于存储该IP数据流状态信息 的两级双向哈希链表；第三步，对于网络中任意到达的IP数据流， 实时更新该两级双向哈希链表；第四步，设定测量周期，定时导出该 两级双向哈希链表中的该IP数据流的状态信息。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该标识域包括：该IP数据流的源IP地址、目的IP地址、 源端口、目的端口、协议号；该长度域包括：每个该IP数据流的报 文数、每个该IP数据流的字节数；该时间域包括：时间戳、相邻报 文的时间间隔；该TCP比特域包括：紧急比特、确认比特、推送比 特、连接复位比特、序号同步、发送方字节流结束比特。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该构建两级双向哈希链表包括：第一步，计算该两级双向 哈希链表的长度；第二步，确定该两级双向哈希链表中任意节点的结 构信息；第三步，确定该IP数据流状态信息在该两级双向哈希链表 中的存储位置。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该计算该两级双向哈希链表的长度包括：第一步，根据网 络运行环境，确定用于存储该两级双向哈希链表的存储空间大小M； 第二步，确定该IP数据流状态信息占用数据大小m；第三步，确定 该两级双向哈希链表的长度比例分别为k％和(100-k)％，得到第一 级双向哈希链表的长度为第二级双向哈希链表的长度 为

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该两级双向哈希链表中任意节点的结构信息包括该节点的 IP数据流状态信息、指向前一相邻节点的地址pre、指向后一相邻节 点的地址next。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该确定该IP数据流在该两级双向哈希链表中的存储位置 包括：第一步，提取该IP数据流状态信息中的源IP地址；第二步， 将该源IP地址对该第一级双向哈希链表的长度L₁做除余运算，得到 该IP数据流状态信息在该第一级双向哈希链表的存储位置；第三步， 将该源IP地址对该第二级双向哈希链表的长度L₂做除余运算，得到 该IP数据流状态信息在该第二级双向哈希链表的存储位置。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该存储空间大小M＝2²³bits，该IP数据流状态信息占用数 据大小m＝100bits，该k％＝60％，该第一级双向哈希链表的长度为 L₁＝50331，该第二级双向哈希链表的长度为L₂＝33554，该IP数据流 的IP源地址为16843009，该IP数据流在该第一级双向哈希链表的存 储位置为L₁[16843009％50331]＝L₁[334]，该IP数据流在该第二级双向 哈希链表的存储位置为L₂[16843009％33554]＝L₂[501]。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该实时更新该两级哈希链表的信息包括：第一步提取，对 任意到达的IP数据流，提取到达IP数据流状态信息；第二步查询， 查询该到达IP数据流状态信息是否存在于该第一级双向哈希链表或 该第二级双向哈希链表；第三步处理，若该到达IP数据流状态信息 存在于该第一级双向哈希链表，则将该到达IP数据流状态信息迁移 至该第一级双向哈希链表的头部；若该到达IP数据流状态信息存在 于该第二级双向哈希链表，则将该到达IP数据流状态信息与该第一 级双向哈希链表尾部已存储的另一IP数据流状态信息进行互换；若 该到达IP数据流状态信息在该第一级双向哈希链表和该第二级双向 哈希链表均不存在，则该到达IP数据流为新IP数据流，将该到达IP 数据流状态信息直接插入第一级双向哈希链表的头部，若此时该第一 级双向哈希链表已满，则将该第一级双向哈希链表尾部的IP数据流 状态信息顺移至该第二级双向哈希链表的头部，若此时第二级双向哈 希链表也已满，将该第二级双向哈希链表中长度最小的IP数据流状 态信息删除。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该第一步提取还包括提取该IP数据流的协议号，若该协 议号为17，则该IP数据流为UDP数据流，进一步提取该UDP数据 流状态信息中的标识域、长度域、时间域；若该协议号为6，则该IP 数据流为TCP数据流，进一步提取该TCP数据流状态信息中的标识 域、长度域、时间域、TCP比特域。

在本发明基于两级双向哈希链表的IP数据流管理方法的另一个 实施例中，该测量周期为1分钟。

本发明的有益效果是：通过本发明提供了一种基于两级双向哈希 链表的IP数据流管理方法，通过构建IP数据流的状态信息和两级双 向哈希链表，对于网络中任意到达的IP数据流，实时更新该两级双 向哈希链表，并每经过一个测量周期，导出两级双向哈希链表中的IP 数据流的状态信息。实现了在高速网络中对IP数据流管理的准确性 和实时性，还能够兼容TCP数据流和UDP数据流，具有很强的扩展 性。

附图说明

图1是根据本发明基于两级双向哈希链表的IP数据流管理方法 一个实施例的流程图；

图2是根据本发明基于两级双向哈希链表的IP数据流管理方法 另一个实施例中计算两级双向哈希链表长度的流程图；

图3是根据本发明基于两级双向哈希链表的IP数据流管理方法 另一个实施例中构建两级哈希链表流程图；

图4是根据本发明基于两级双向哈希链表的IP数据流管理方法 另一个实施例中确定IP数据流在两级哈希链表中存储位置的流程图。

图5是根据本发明基于两级双向哈希链表的IP数据流管理方法 另一个实施例中实时更新所述两级哈希链表信息的流程图。

具体实施方式

为了便于理解本发明，下面结合附图和具体实施例，对本发明进 行更详细的说明。附图中给出了本发明的较佳的实施例。但是，本发 明可以以许多不同的形式来实现，并不限于本说明书所描述的实施 例。相反地，提供这些实施例的目的是使对本发明的公开内容的理解 更加透彻全面。

需要说明的是，除非另有定义，本说明书所使用的所有的技术和 科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。 在本发明的说明书中所使用的术语只是为了描述具体的实施例的目 的，不是用于限制本发明。本说明书所使用的术语“和/或”包括一个或 多个相关的所列项目的任意的和所有的组合。

图1显示了本发明基于两级双向哈希链表的IP数据流管理方法 一个实施例的流程图。其中，第一步S101，构建IP数据流状态信息， 该状态信息包括：标识域、长度域、时间域、和/或TCP比特域；第 二步S102，构建用于存储该IP数据流状态信息的两级双向哈希链表； 第三步S103，对于网络中任意到达的该IP数据流，实时更新该两级 双向哈希链表；第四步S104，设定测量周期，定时导出该两级双向 哈希链表中的该IP数据流的状态信息。

作为优选实施例，对于第一步S101中的IP数据流状态信息中的 各个域又进一步细化为：

标识域包括：该IP数据流的源IP地址、目的IP地址、源端口、 目的端口、协议号。例如“192.168.1.1、192.168.2.1、80、8192、6” 标识了一个IP数据流信息，其中“192.168.1.1”是源IP地址， “192.168.2.1”是目的IP地址，“80”是源端口，“8192”是目的端 口，“6”是协议号。

长度域包括：每个IP数据流的报文数、每个IP数据流的字节数。 用于统计每个IP数据流所包括的报文数和字节数。另外，对于IP数 据流还可以进一步分为长IP数据流和短IP数据流，通常是将单位时 间内报文数超过某个固定阈值的IP数据流定义为长IP数据流，而将 单位时间内报文数少于和等于该相同阈值的IP数据流定义为短IP数 据流。

时间域包括：时间戳、相邻报文的时间间隔。其中，时间戳记录 了每个IP数据流的开始时间和结束时间，而相邻报文的时间间隔表 明了每个IP数据流的服务质量情况。

TCP比特域包括：紧急比特(英文缩写为URG)、确认比特(英 文缩写为ACK)、推送比特(英文缩写为PSH)、连接复位比特(英文 缩写为RST)、序号同步(英文缩写为SYN)、发送方字节流结束比特 (英文缩写为FIN)，分别对应TCP数据流的紧急、确认、推送、复位、 同步、结束等状态。

与现有技术相比，通过第一步S101构建的IP数据流状态信息中 的标识域可以与其他三域进行有选择的组合使用。例如，对于TCP 数据流则要有该TCP比特域，对于其他类型的IP流无需使用TCP比 特域。这种灵活的组合方式，有利于适用于不同的网络环境和针对不 同网络数据流类型，能够增强本发明的适应性。

对于图1中的第二步S102，构建用于存储该IP数据流状态信息 的两级双向哈希链表。

其中，构建哈希链表的主要原因在于能够通过选择适合的哈希函 数将每个IP数据流的状态信息映射为哈希链表的地址序号，从而支 持一次运算就能实现在哈希链表中成功查找到该IP数据流状态信息 的目的。这种基于哈希链表的实现方法是一种支持集合快速表示和查 询的数据结构，它以O(1)元素查询时间复杂度和较低的计算复杂度等 优点被广泛应用在路由查询、数据库查询等领域。另外，采用双向的 哈希链表还能够从该链表中直接确定一个节点的前趋(即前一个结点 的地址)，使得插入和删除操作无需遍历整个链表。因此，本发明实 施例将哈希查找方法和双向链表相结合构造双向哈希链表，用来提高 对IP数据流管理的实时性。

而对于采用两级的双向哈希链表，其主要原因在于互联网络中 的IP数据流通常服从“重尾分布”，即：少数长IP数据流占据了网 络的大部分流量，而大量短IP数据流占据了网络的小部分流量。 因此，在诸如网络计费、热点事件发现、队列管理等实际应用中， 只需要重点关注长IP数据流的状态信息，没必要关注每一个IP数 据流的状态信息，特别是长度较短的IP数据流。因此，对长IP数 据流的维护质量直接决定了对IP数据流管理的准确程度。这样，可 以利用两级双向哈希链表，避免因大量出现的短IP数据流将长IP 数据流挤出链表的现象，使得频繁访问的长IP数据流更准确的被 缓存。

为此，本发明实施例中构建第一级双向哈希链表，用于存储“最 近频繁使用”的IP数据流，即始终保持最新到达的IP数据流状态信 息置于第一级双向哈希链表的头部；反之，最久未到达的IP数据流 状态信息则保留在第一级双向哈希链表的尾部。其实质是长IP数据 流的报文数目多，访问该第一级双向哈希链表频繁，始终处于该链 表的头部，而对于短IP数据流，其报文数目少，很少访问该链表， 则始终处于该链表的尾部。因此，这种基于“最近频繁使用”的原 则，可实现长IP数据流的快速过滤。

但是，若只有第一级双向哈希链表，当网络中短时间出现大量 短IP数据流时，例如DDoS攻击，这些大量出现的短IP数据流状态 信息将会处于该链表的头部，使得长IP数据流状态信息被挤出，出 现长IP数据流状态信息被误删现象，降低了IP数据流管理的准确性。 基于此，当第一级双向哈希链表空间耗尽时，需要有第二级双向哈 希链表，将第一级链表删除的IP数据流状态信息缓存在第二级双向 哈希链表。再者，第二级双向哈希链表采用“最少最远使用”原则， 将第二级双向哈希链表中最少访问的IP数据流状态信息(即包含报 文数最少的流)剔除。因此，第二级双向哈希链表通过缓存第一级 双向哈希链表删除的IP数据流状态信息，尽可能暂存第一级链表误 删的长IP数据流状态信息，降低长IP数据流状态信息被误删的可能 性，并且还能保存该长IP数据流的状态信息。

以上对本发明实施例采用两级双向哈希链表的原因及作用效 果进行了说明。对于图1中的第二步S102，图2则进一步显示了构 建两级双向哈希链表实施例的流程图。

在图2中，第一步S201，计算该两级双向哈希链表的长度；第 二步S202，确定该两级双向哈希链表中任意节点的结构信息；第三 步S203，确定该IP数据流状态信息在该两级双向哈希链表中的存储 位置。

其中，对于第一步S201计算该两级双向哈希链表的长度，图3 又进一步显示了实现计算两级双向哈希链表长度的一个优选实施 例。

如图3所示，第一步S301，根据网络运行环境，确定用于存储 该两级双向哈希链表的存储空间大小M。例如，M＝2²³bits。

第二步S302，确定IP数据流状态信息占用数据大小m。例如， m＝100bits。

第三步S303，确定该两级双向哈希链表的长度比例分别为k％ 和(100-k)％，得到第一级双向哈希链表的长度为第 二级双向哈希链表的长度为例如，k％＝60％。这 样当M＝2²³bits，m＝100bits时，可以得到第一级双向哈希链表的长 度为L₁＝50331，表示第一级双向哈希链表可以存储50331个IP数据 流状态信息，第二级双向哈希链表的长度为L₂＝33554，表示第二级 双向哈希链表可以存储33554个IP数据流状态信息。

对于图2中的第二步S202，其中的两级双向哈希链表中任意节 点的结构信息的一个优选实施例包括：该节点的IP数据流状态信息、 指向前一相邻节点的地址pre、指向后一相邻节点的地址next。

对于图2中的第三步S203，图4又进一步显示了确定IP数据 流状态信息在两级双向哈希链表中的存储位置的一个优选实施例。

如图4所示，第一步S401，提取该IP数据流状态信息中的源 IP地址。例如，一个IP数据流的IP源地址为0x1010101＝16843009。

第二步S402，将该源IP地址对第一级双向哈希链表的长度L₁做 除余运算，得到该IP数据流状态信息在该第一级双向哈希链表的存 储位置。这里的除余运算是在相除后取余数。例如，承接上述实施 例，IP源地址为16843009，第一级双向哈希链表的长度为L₁＝50331， 该IP数据流状态信息在该第一级双向哈希链表的存储位置为 L₁[16843009％50331]＝L₁[334]，即该链表第334个结点L₁[334]为该该 IP数据流状态信息的存储位置。

第三步S403，将该源IP地址对第二级双向哈希链表的长度L₂做 除余运算，得到该IP数据流状态信息在该第二级双向哈希链表的存 储位置。承接上述实施例，IP源地址为16843009，第二级双向哈希 链表的长度为L₂＝33554，可得该IP数据流状态信息在第二级双向哈 希链表的存储位置为L₂[16843009％33554]＝L₂[501]，即该链表第501 个结点L₂[501]即为该IP数据流状态信息的存储位置。

这样，通过图2至图4所示实施例，明确了如何构建两级双向 哈希链表。以下将继续结合图1中的第三步S103，具体说明如何对 构建好的两级双向哈希链表进行不断更新。

图5是根据本发明基于两级双向哈希链表的IP数据流管理方 法另一个实施例中实时更新两级双向哈希链表信息的流程图。其中， 第一步提取S501，对任意到达的IP数据流，提取该到达IP数据流 状态信息；第二步查询S502，查询该到达IP数据流状态信息是否存 在于第一级双向哈希链表或第二级双向哈希链表；第三步处理S503， 若该到达IP数据流状态信息存在于第一级双向哈希链表，则将该到 达IP数据流状态信息迁移至第一级双向哈希链表的头部；若该到达 IP数据流状态信息存在于所述第二级双向哈希链表，则将该到达IP 数据流状态信息与第一级双向哈希链表底部已存储的另一IP数据流 状态信息进行互换；若该到达IP数据流状态信息在第一级双向哈希 链表和第二级双向哈希链表均不存在，则该到达IP数据流为新IP数 据流，将该到达IP数据流状态信息直接插入第一级双向哈希链表的 头部，若此时第一级双向哈希链表已满，则将第一级双向哈希链表 尾部的IP数据流状态信息顺移至第二级双向哈希链表的头部，若此 时第二级双向哈希链表也已满，则将第二级双向哈希链表中长度最 小的IP数据流状态信息删除。

其中，第二步S502中查询到达IP数据流状态信息是否存在于 第一级双向哈希链表或第二级双向哈希链表的一个优选实施例方 法是：用该到达IP数据流状态信息中的源IP地址对第一级双向哈 希链表的长度L₁做除余运算得到j，然后找到第一级双向哈希链表 第j个位置L₁[j]存储的IP数据流状态信息，比较这两个IP数据流状 态信息的标识域是否相等，若相等，则判定该到达IP数据流状态信 息已存在于第一级双向哈希链表中，否则就不存在于第一级双向哈 希链表中。是否存在于第二级双向哈希链表的查询判定方法与上述 类似，不再赘述。这种查询判定方法，仅需要两次并行的哈希运算 即可获知到达IP数据流状态信息的存储位置，具有很好的实时性处 理效果。

进一步，根据图5所示实施例，处理一个到达IP数据流所需 要的最长流程包括：查询该到达IP数据流状态信息是否存在于第一 级双向哈希链表(需要1次访存操作)、查询该到达IP数据流状态 信息是否存在于第二级双向哈希链表(需要1次访存操作)、直接将 该到达IP数据流状态信息插入第一级双向哈希链表的头部(需要1 次访存操作)、若第一级双向哈希链表已满，则将第一级双向哈希链 表尾部的IP数据流状态信息顺移至第二级双向哈希链表的头部(需 要2次访存操作)、若第二级双向哈希链表也已满，则将第二级双向 哈希链表中长度最小的IP数据流状态信息删除(需要1次访存操作) 步骤。最多总共需要6次访存操作。

在高速网络环境中，若一次高端片内SRAM访问的时间为4ns， 则完成一次更新两级双向哈希链表信息所需的时间为4ns×6＝24ns， 小于OC-768线路的25ns的要求，可满足链路数据传输速率40Gbps 以下的骨干网上流量的实时测量。因此，采用本发明基于两级双向 哈希链表的IP数据流管理方法实施例具有很高的处理实时性。

对于图5中的第一步提取S501还包括提取该到达IP数据流的 协议号，根据该协议号的不同进一步确定该到达IP数据流的类型以 及有选择性的提取其中的部分或全部状态信息。具体包括：若该协 议号为17，则该到达IP数据流为UDP数据流，进一步提取该UDP 数据流状态信息中的标识域、长度域、时间域；若该协议号为6， 则该到达IP数据流为TCP数据流，进一步提取该TCP数据流状态信 息中的标识域、长度域、时间域、TCP比特域。由此，可以增强本 发明基于两级双向哈希链表的IP数据流管理方法应用的扩展性和针 对性，能够兼容TCP数据流和UDP数据流。

对于图1中的第四步S104，其中的测量周期是指将整个IP数 据流的管理时间划分成多个等长的测量周期，每隔一个测量周期， 例如该测量周期为1分钟，将该两级双向哈希链表中存储的IP数据 流状态信息全部导出，并初始化两级双向哈希链表中的IP流状态信 息中的各域值为0。

通过本发明提供了一种基于两级双向哈希链表的IP数据流管 理方法，通过构建IP数据流的状态信息和两级双向哈希链表，对于 网络中任意到达的IP数据流，实时更新该两级双向哈希链表，并每 经过一个测量周期，导出两级双向哈希链表中的IP数据流的状态信 息。实现了在高速网络中对IP数据流管理的准确性和实时性，还能 够兼容TCP数据流和UDP数据流，具有很强的扩展性。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范 围，凡是利用本发明说明书及附图内容所作的等效结构变换，或直 接或间接运用在其他相关的技术领域，均包括在本发明的专利保护 范围内。