Cuckoo Bags for Exploring Multikey Data

摘要

As the transition from IPv4 to hybrid IPv4/IPv6 networks begins, our structures for representing IP addresses for analysis are lagging behind. There is a need for tools that can develop behavioral models of network traffic that include communications patterns among hosts. This work introduces the CuBag data structure and tools for maintaining sets indexed by IPv4 and IPv6 addresses in the same structure. The current tools, rwset and rwbag, in the SiLK tool suite use pointer structures developed for IPv4 but have no support for IPv6 addresses. CuBag keys can contain multiple SiLK record fields, including IPv4 and IPv6 addresses. They use multiple hash functions for key insertion and lookup in constant time. We describe CuBags and illustrate their use with two small case studies.