Unlike the current Internet where applications have little control over the path that their data travels, emerging network architectures enable applications to control the path their packets/flows take. Although an application can select its paths, providing an application with the up-to-date information needed to make an informed decision is a difficult problem. In particular, monitoring (i.e., collecting performance information about) a network the size of the Internet presents serious scalability challenges. In this paper, we present a network monitoring service that can provide applications with up-to-date network information, yet scale to the size of the Internet. Our network monitoring service dynamically selects and enables/disables monitoring points to focus on paths currently needed by applications. We present experimental results based on real-world traffic traces that show our system can provide up-to-date information for 80% of the paths used by applications by monitoring as few as 100 strategically identified locations in the Internet.