Automatic Test Packet Generation

‡ These authors contributed equally to this work. Networks are getting larger and more complex; yet adminis-trators rely on rudimentary tools such as ping and tracer-oute to debug problems. We propose an automated and sys-tematic approach for testing and debugging networks called “Automatic Test Packet Generation ” (ATPG). ATPG reads router configurations and generates a device-independent model. The model is used to generate a minimum set of test packets to (minimally) exercise every link in the network or (maxi-mally) exercise every rule in the network. Test packets are sent periodically and detected failures trigger a separate mech-anism to localize the fault. ATPG can detect both func-tional (e.g., incorrect firewall rule) and performance prob-lems (e.g., congested queue). ATPG complements but goes beyond earlier work in static checking (which cannot detect liveness or performance faults) or fault localization (which only localize faults given liveness results). We describe our prototype ATPG implementation and re-sults on two real-world data sets: Stanford University’s back-bone network and Internet2. We find that a small number of test packets suffices to test all rules in these networks: For example 4000 packets can cover all rules in Stanford back-bone network while 54 is enough to cover all links. Sending 4000 test packets 10 times per second consumes less than 1 % of link capacity. ATPG code and the data sets are pub-licly available [6]. 1