Algorithm

Each packet (or every $n$th packet) that is routed causes packet rates in applicable nodes in the tree to be updated; starting in the root, and going down to the deepest available node. This works as follows. The first byte of the IP destination address of a forward packet is used as an index in the root node to find the record in which to update the to-rate. For reverse packets the first byte of the IP source address is used as an index in the root node to find the record in which to update the from-rate. If the record has a child, the process descends down to the child and continues. If no child exists, it is created if either the from-rate or the to-rate exceeds a certain threshold. In any case, the process may follow the pointer in the record to the child node. In this child node, the second byte of the IP address is used as an index to find the record and update the packet rates. This process may descend down to the deepest level in the tree where per-IP address packet rates are kept. The full algorithm is given in pseudo-code in Algorithm 4.1.

Method $\CALL{update}$ is called by method $\CALL{handle\_packet}$ described in Section 5.2. Parameter $addr$ is the 4-byte IP source or destination address of packet $packet$, depending on whether MULTOPS is set up in victim-oriented or attacker-oriented mode. Parameter $fwd$ tells $\CALL{update}$ whether this packet is a forward packet or a reverse packet. Statement 1 immediately after the $\FOR$-loop annotates the packet with r's from-rate and to-rate. This annotation can later be used by a part of the system that implements the heuristic to determine whether or not this packet is part of a malicious flow and should, thus, be dropped.