iPlane is a scalable service providing accurate predictions of Internet path performance for emerging overlay services. Unlike the more common black box latency prediction techniques in use today, iPlane builds a structural model of the Internet. We construct an annotated map of the Internet and predict end-to-end performance by composing measured performance of segments of known Internet paths. We have studied the feasibility and utility of the iPlane service by applying it to several representative overlay services in use today: content distribution, swarming peer-to-peer filesharing, and voice-over-IP.