Metrics

We evaluate our heuristics using three metrics:

• Average core size: $\vert\mbox{\emph{Core}$(h)$}\vert$ averaged over all $h \in {\cal H}$. This metric is important because it determines how much capacity is available in the system. As the average core size increases, the total capacity of the system decreases.

• Maximum load: The load of a host $h^\prime$ is the number of cores $\mbox{\emph{Core}$(h)$}$ of which $h^\prime$ is a member. The maximum load is the largest load of any host $h^\prime \in {\cal H}$.

• Average coverage: We say that an attribute $a$ of a host $h$ is covered in Core$(h)$ if there is at least one other host $h^\prime$ in Core$(h)$ that does not have $a$. Thus, an exploit of attribute $a$ can affect $h$, but not $h^\prime$, and so not all hosts in Core$(h)$ are affected. The coverage of Core$(h)$ is the fraction of attributes of $h$ that are covered. The average coverage is the average of the coverages of Core$(h)$ over all hosts $h \in {\cal H}$. A high average coverage indicates a higher resilience to Internet catastrophes: many hosts have most or all of their attributes covered. We return to this discussion of what coverage means in practice in Section 5.3, after we present most of our simulation results for context.

For brevity, we use the terms core size, load, and coverage to indicate average core size, maximum load, and average coverage, respectively. Where we do refer to these terms in the context of a particular host, we say so explicitly.

A good heuristic will determine cores with small size, low load, and high coverage. Coverage is the most critical metric because it determines how well it does in guaranteeing service in the event of a catastrophe. Coverage may not equal 1 either because there was no host $h^\prime$ that was available to cover an attribute $a$ of $h$, or because the heuristic failed to identify such a host $h^\prime$. As shown in the following sections, the second case rarely happens with our heuristics.

Note that, as a single number, the coverage of a given Core$(h)$ does not fully capture its resilience. For example, consider host $h_1$ with two attributes and host $h_2$ with 10 attributes. If Core$(h_1)$ covers only one attribute, then Core$(h_1)$ has a coverage of 0.5. If Core$(h_2)$ has the same coverage, then it covers only 5 of the 10 attributes. There are more ways to fail all of the hosts in Core$(h_2)$ than those in Core$(h_1)$. Consequently, we also use the number of cores that do not have a coverage of 1.0 as an extension of the coverage metric.