A simple conceptual generator for the Internet graph

The evolution of the Internet during the last years, has lead to a dramatic increase in the size of its representation as a graph at the Autonomous System (AS) level. Reproducing a smaller size snapshot of the AS graph is important for studying protocols in realistic settings. The objective of our work, is to create a generator that accurately emulates and reproduces the distinctive properties of the Internet graph. Our approach is based on (a) the incorporation of the jellyfish-like structure of the Internet and (b) the consideration of the peer-to-peer and customer-provider relations between ASs. We are the first to capture the distinctive structure of the Internet graph together with utilizing the information provided by the AS relationships in order to create a tool for generating a realistic representation. Compared with existing generators, our tool does not try to satisfy specific metrics; instead, it tries to remain faithful to the conceptual model of the Internet structure. In addition, our approach can lead to (i) the identification of important attributes and patterns in the Internet AS topology, and (ii) the extraction of valuable information on various relationships between ASs and the corresponding impact on the Internet structure.We implement our graph generator and evaluate it using one of the largest and most recent datasets for the AS topology. Our evaluations clearly show the ability of our tool to capture the structural properties of the Internet topology at the AS level with high accuracy. Finally, we discuss how our generator can not only reproduce, but also shrink the input graph while maintaining its unique structure and properties.