Firmware architecture

The following block diagram shows the organisation of the FlowMon firmware.

Block diagram of FlowMon firmware

Network packets are received through one of the ports (top left) and immediately copied to the other port, thus realising the repeater function. Another copy of each packet is sent to the flow-processing engine. Actually, as we can see in the diagram, each input port is being served by two identical header-processing pipelines. The SPLIT units feeds them with packets on a round-robin basis.

The IBUF units buffer the incoming packets and also implement the optional statistical sampling (see Sampling below).

The next unit is HFE (Header Field Extractor). Its task is to parse the packet headers, extract relevant fields from them, add other context such as timestamp or port identifier, and pack all this information into a fixed data structure named Unified Header (UH). Unified Headers from all four header-processing pipelines are then merged together and follow the same path. The UHFIFO and UHDRV units keep an eye on proper UH sequencing.

The stream of Unified Headers is then divided into two branches: One copy of each UH is inserted into the statistical FIFO queue and waits there till it is removed by the SCTRL unit at the very end of the processing.

The other branch deals with classification. The HASH unit takes five key fields from the UH and computes a hash value from them. The key fields are: source and destination IP addresses, source and destination ports and protocol number. Optionally, selected bits of the key fields can be masked so that the hash value is computed only from the remaining (unmasked) bits. This results in more aggregated flows. The HASH unit uses the CRC-64 function, more details are given in the Hashing section below.

The computed hash now uniquely determines the flow the packet belongs to. The HASH unit inserts the hash values into the hash FIFO. At the opposite end, the HSRCH unit removes them from this queue and performs a look-up in the index that contains hashes of all flows that are currently contained in the flow cache. The result of the look-up is reported to the MAN unit. The HSRCH unit also implements the sample-and-hold procedure (see Sampling below).

The next unit, MAN, (Manager) keeps track of the state of active flows and free memory locations. Flow states are held in a bidirectional list sorted by the timestamps. This way, inactive flows (those with oldest timestamps) are easily identified and MAN then instructs the SCTRL unit to export them.

Finally, the SCTRL units manages the flow cache. The flow cache is currently implemented in static RAM and can hold up to 65536 flows. Depending on the instructions from MAN, for each packet SCTRL either creates a new records or changes an existing one. In both cases, flow statistics are set/updated using the corresponding UH taken from the statistical FIFO. SCTRL also passes the expired flows to the host operating system.

More information about the firmware design can be found in the technical report [ZL05].

Sampling

The FlowMon firmware implements two variants of packet sampling:

1. statistical sampling
2. sample-and-hold

The first variant is implemented in the IBUF units and randomly selects incoming packets for further processing. The sampling procedure is governed by a numeric parameter known as sampling rate: Packets are selected with probability 1/R_s, where R_s is the sampling rate.

The second variant – sample-and-hold – adds another twist to the statistical sampling: packets belonging to flows that already exist in the flow cache are immune to sampling. Other packets are randomly sampled with probability 1/R_h. The sampling rate R_h is independent of the sampling rate R_s above. The sample-and-hold procedure must check the contents of the flow cache and is thus implemented later in the flow processing chain, namely in the HSRCH unit.

Hashing

Packets are classified as belonging to a certain flow according to the hash value computed from the five key fields using the CRC-64 polynomial. Actually, only 57 out of 64 bits of the CRC-64 value are taken as the unique flow identifier.

The use of hashing was necessary because the concatenated key fields are simply too long, especially for IPv6 packets. Of course, hashing can lead to collisions when different key fields map to the same hash value. Since the distribution of CRC-64 values is uniform, the collision probability is given by the ratio of the number of flow in the cache and the number of all possible hash values. The capacity of the flow cache is 2¹⁶ flows, so the collision probability is at most 2¹⁶/ 2⁵⁷= 2^-41. At the traffic rate of 1 million packets per second, we can expect about 15 collisions per year on the average.

Such a collision probability looks reasonable but we also have to take into account the possibility of a provoked collision. The CRC-64 function is well-known and if the hash values were deterministic, an attacker might be able to find a collision in advance and then cover her traces by first injecting a carefully forged flow into the cache and then starting a hostile network activity that will classified as belonging to the previous (bogus) flow. To counter this threat, the CRC-64 algorithm is initialised with a random value so that the outcome of the hash function cannot be determined in advance.

Technical report [Hla05] contains a detailed analysis and verification of the CRC-64 algorithm as implemented in the HASH unit.

References