Auto-discovery is one of the key technologies that enables management systems to be quickly customized to the environments that they are intended to manage. As Internet services have grown in complexity in recent years, it is no longer sufficient to monitor and manage these services in isolation. Instead, it is critical that management systems discover dependencies that exist among Internet services, and use this knowledge for correlation of measurement results, so as to determine the root-causes of problems. While most existing management systems have focussed on discovery of host, servers, and network elements in isolation, in this paper, we describe auto-discovery techniques that discover relationships among services. Since new Internet services and service elements are being deployed at a rapid pace, it is essential that the discovery methodologies be implemented in an extensible manner, so that new discovery capabilities can be incrementally added to the management system. In this paper, we present an extensible architecture for auto-discovery and describe a prototype implementation of this architecture and associated auto-discovery techniques. We also highlight experiences from applying these techniques to discover real-world ISP systems. Although described in the context of ISP systems, the concepts described in this paper are applicable for the discovery of services and inter-service relationships in enterprise systems as well. 18 Pages