Patent ID: 7669241
Filing Date: 2010-02-23
Classification: H04L

Abstract:
1. A method of maintaining a data-structure capable of providing an approximate distinct-count of data-elements, said method comprising the steps of: obtaining a plurality of data-elements including a source value comprising a source IP address and a destination value comprising a destination IP address; using a processor for generating an indexed set of samples of said data-elements, each of said samples having a sample rate that is an exponentially decreasing function of the index of said sample; hashing said data-elements contained in one of a set of first-level hash buckets to a set of second-level hash buckets wherein hashing is performed using an address pair formed by combining said source value and said destination value; associating a set of count signatures with a first one of said samples, each of said count signatures comprising a total-element count and a bit-location count, wherein the associating comprises associating one of said count signatures with each of said second-level hash buckets; determining a set of distinct-source, half-open connection frequencies for the destination addresses; and determining whether any of the destinations has a frequency that increases in a manner that is indicative of a distributed denial of service attack including distinguishing between a distributed denial of service attack and a legitimate surge in traffic based on an increase in a volume of data and an associated change in half-open connections of the frequency increase.