Using network motifs to investigate the influence of network topology on PPM-based IP traceback schemes

Multiple schemes that utilize Probabilistic Packet Marking (PPM) have been proposed to deal with Distributed Denial of Service (DDoS) attacks by reconstructing their attack graphs and identifying the attack sources. By analyzing a set of PPM-based schemes, we show that past researchers have evaluated the schemes using disparate and often inadequate underlying topologies, which makes a side-by-side comparison of the scheme performance a complex problem. To tackle this problem, we evaluate selected schemes on a large set of Internet-like topologies and adapt the network motif approach to provide a common ground for comparing the schemes' performances in different network topologies. This approach allows us to determine the level of structural similarity between network topologies and consequently enables the comparison of scheme performance even when the schemes are implemented on different topologies. Our results reveal that both the value of the PPM-based schemes' convergence times, and their rankings vary depending on the underlying network topology. However the variation is considerably less when the topologies are compared within superfamilies of structural similarity. More specifically, the standard deviation in convergence times across the networks drops to about a tenth of its original value when the set of 28 networks are arranged in four superfamilies. To complement our results, we present an analytical model showing a link between scheme performance in any superfamily, and the motifs exhibited by the networks in that superfamily. Our work proposes an effective way of comparing general network protocol performance in which the protocol is evaluated on specific representative networks instead of an entire set of networks.