Check out the new USENIX Web site. next up previous
Next: Defining Similarity Up: Role Classification of Hosts Previous: System Overview


Model

In this section, we develop a model for thinking about the grouping problem. We define the problem in the abstract, providing a model with several functions and parameters that can be adjusted to meet various goals. Later in the paper, we present and evaluate instantiations of these parameters. We extend this definition of similarity to define the average similarity between a host h1 and a group G2, avg_similarity(h1, G2), as the ratio of the sum of the similarity between h1 and each $h_2 \in G_2$ to the number of hosts in G2:

\begin{displaymath}
\textit{avg\_similarity}(h_1, G_2) = \frac{\sum_{h_2\in G_2}{\mbox{\emph{similarity}}(h_1, h_2)}}{\vert G_2\vert}
\end{displaymath}

A partitioning P of I respects avg_similarity if for all $h_1 \in G_1$ and $G_2 \in P$, avg_similarity $(h_1, G_1) \geq$ avg_similarity(h1, G2). Respecting similarity or avg_similarity is not sufficient to generate a useful partitioning of I. After all, a partitioning that puts all the nodes in one group or one that puts each node in a separate group respects similarity. We therefore provide a parameter that can be used by network administrators to control how aggressive the algorithm is in partitioning I into groups.

Subsections
next up previous
Next: Defining Similarity Up: Role Classification of Hosts Previous: System Overview
Godfrey Tan 2003-04-01