NETWORK TRAFFIC MAPPING AND PERFORMANCE ANALYSIS

An overlay network analysis method obtains data including but not limited to client packet traffic data on an overlay network, and performs one or more analyses based on the obtained data to generate and output topological and/or performance information for the overlay network and/or the network substrate on which the overlay network is implemented. Client traffic data collected for specific client resource instances may be analyzed to generate performance metrics for the overlay network between the instances. Aggregated client traffic data for specific clients may also be analyzed to generate mappings of the clients' private network implementations on the overlay network, as well as performance metrics for the clients' private networks on the overlay network. In addition, client traffic data from multiple clients may be aggregated and analyzed to generate mappings and performance metrics for the overlay network as a whole.