PNRP (peer name resolution protocol) is a decentralized name resolution and routing protocol built into the Windowstrade operating system that creates an Internet-scale peer-to-peer structured overlay. Ensuring the protocol's performance in Internet scale presents a critical challenge. We describe Internet scale testing of PNRP using a distributed network simulator, WiDS. We use real-world Internet characteristics and PNRP node behaviors to simulate the Internet environment, assess PNRP performance, and support protocol debugging. A case study demonstrates identification of a protocol flaw that could otherwise only be discovered through full-scale deployment experience