Expansion and contraction

If the to-rate or the from-rate for an address with an $n$-bit prefix $P$ exceeds the expand threshold, MULTOPS creates a child node under the record for prefix $P$ to keep track of packet rates for addresses with $(n+8)$-bit prefix $P'$. Lowering this expand threshold increases precision of MULTOPS, but also increases its memory use. Figure 3 shows how a new node is added to the tree to keep track of all packet rates to and from addresses with prefix 130.16.120.

The reverse of expansion is contraction. Contracting a record involves removing a subtree from under a record. A subtree is contracted when the aggregate packet rate for that subtree drops below $R_{max}$. Contraction is done to constrain memory use and to avoid (maliciously intended) memory exhaustion. Figure 3 shows how a node is contracted.

Figure 3: Expansion and contraction

Traversing the entire tree in search of subtrees to contract is potentially expensive and its frequency should be chosen with care. Traversing the tree for every $x$ routed packets is dangerous because a router should have its resources free for routing, not for contracting when packet rates go up. Traversing the tree every $t$ ms is safer, but choosing $t$ correctly is tricky: if $t$ is too high, memory might run out before traversal starts. The strategy we chose is to never allocate more memory than a certain limit $m$--thereby making memory exhaustion impossible--and to traverse the tree every $t$ ms in search of subtrees to contract. In the time period between reaching memory limit $m$ and the next ``cleanup,'' MULTOPS cannot create new nodes. It is, therefore, important to choose $t$ low, but not so low as to trigger cleanups too often and, thus, waste the router's resources.

An attacker might try to launch a memory exhaustion attack against MULTOPS by causing it to branch profusely. The two opposing forces are the attacker causing nodes to be created versus contraction causing nodes to be destroyed. Since a subtree is contracted when the packet rates to and from addresses with a certain prefix are less than the expand threshold, the attacker will have to sustain a higher packet rate for as many different address prefixes as possible. Section 5.4 deals with this issue in a quantitative context.