1

我目前正在为我的网络上的传出 TCP 和 UDP 数据包存储 IP 地址和端口。我监视网络并等待对这些数据包的响应。

通过在 IP 地址和端口列表中搜索过去的出站数据包,首先检查进入网络的每个数据包以查看它是被请求的还是未经请求的。

目前,我使用一个被锁定的动态数组,然后搜索到达网络的每个数据包。在我们升级到 100 mbps 服务之前,这一直很好。正如我们的分析器所指出的那样,在高峰时间,我们在搜索功能中存在很多争用。

查看了很多不同的算法,我没有发现很多适合这种特定类型的使用。我看过的大多数细节原子插入和原子访问,总体上非常简单。

我在想,首先复制数组,搜索它,如果找到它就删除它,然后对两个数组引用/指针进行比较和交换,这可能是一种改进。如果 CAS 成功了,那很好。如果没有,那么再做一遍,直到它完成为止。

但是,这会占用大量内存,我想它可能会降低性能。我们有很多内存要使用,但我相信在高峰期,会有很多 CAS 失败。

我将致力于此实现以进行一些分析,但我很好奇是否有其他人曾经提出过解决此问题的方法并愿意分享。尽管我使用 C 和 C# 工作,但任何语言的示例都很好。

4

2 回答 2

1

我宁愿使用字典数据结构来解决您的问题。您可以使用ConcurrentDictionary 或创建自己的并使用无锁链表(网络上有很多参考资料)来处理冲突。

于 2013-07-07T18:09:17.003 回答
0

听起来您有一个包含所有过去 IP 地址和端口的数组,以及访问它的多个进程。这将解释“搜索争用”:不是两个搜索之间的争用,而是当整个数组正在由其他进程之一写入时任何搜索的争用。

我想像 B-tree 这样的东西可以缓解你的问题。搜索时间从 O(N) 下降到 O(log N),写入只会更改(并因此导致争用)一小部分数据。很可能已经存在专门针对 IP 地址和端口的 B-tree 变体数据结构和算法;这似乎有点类似于存储和转发开关。一篇看起来很接近的论文是http://www.rhsmith.umd.edu/faculty/cdell/papers/ieee96.pdf

于 2013-07-06T22:37:39.420 回答